# Dima and Figure

Dima loves making pictures on a piece of squared paper. And yet more than that Dima loves the pictures that depict one of his favorite figures.

A piece of squared paper of size n × m is represented by a table, consisting of n rows and m columns. All squares are white on blank squared paper. Dima defines a picture as an image on a blank piece of paper, obtained by painting some squares black.

The picture portrays one of Dima’s favorite figures, if the following conditions hold:

• The picture contains at least one painted cell;
• All painted cells form a connected set, that is, you can get from any painted cell to any other one (you can move from one cell to a side-adjacent one);
• The minimum number of moves needed to go from the painted cell at coordinates (x 1, y 1) to the painted cell at coordinates (x 2, y 2), moving only through the colored cells, equals |x 1 - x 2| + |y 1 - y 2|.

Now Dima is wondering: how many paintings are on an n × m piece of paper, that depict one of his favorite figures? Count this number modulo 1000000007 (109 + 7).

Input

The first line contains two integers n and m — the sizes of the piece of paper (1 ≤ n, m ≤ 150).

Output

In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

Examples

input

2 2

output

13

input

3 4

output

571

Solution:

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>

using namespace std;

const int md = 1000000007;

void add(int &a, int b) {
a += b;
if (a >= md) a -= md;
}

int f[155][155][2][2], oldf[155][155][2][2], trueoldf[155][155][2][2];

int main() {
int n, m;
scanf("%d %d", &n, &m);
memset(f, 0, sizeof(f));
for (int a=1;a<=m;a++)
for (int b=a;b<=m;b++) f[a][b][1][1] = 1;
int ans = 0;
for (int i=1;i<=n;i++) {
long long cnt = 0;
for (int a=1;a<=m;a++)
for (int b=a;b<=m;b++)
for (int ka=0;ka<=1;ka++)
for (int kb=0;kb<=1;kb++) cnt += f[a][b][ka][kb];
ans = (ans+cnt*(n-i+1)) % md;

for (int a=1;a<=m;a++)
for (int b=a+1;b<=m;b++)
for (int kb=0;kb<=1;kb++) {
}
for (int a=1;a<=m;a++)
for (int b=m;b>=a+1;b--)
for (int ka=0;ka<=1;ka++) {
}
for (int a=m;a>=2;a--)
for (int b=a;b<=m;b++)
for (int kb=0;kb<=1;kb++) {