Joisino has a lot of red and blue bricks and a large box. She will build a tower of these bricks in the following manner.

First, she will pick a total of N bricks and put them into the box. Here, there may be any number of bricks of each color in the box, as long as there are N bricks in total. Particularly, there may be zero red bricks or zero blue bricks. Then, she will repeat an operation M times, which consists of the following three steps:

* Take out an arbitrary brick from the box.
* Put one red brick and one blue brick into the box.
* Take out another arbitrary brick from the box.



After the M operations, Joisino will build a tower by stacking the 2 \times M bricks removed from the box, in the order they are taken out. She is interested in the following question: how many different sequences of colors of these 2 \times M bricks are possible? Write a program to find the answer. Since it can be extremely large, print the count modulo 10^9+7.

Constraints

* 1 \leq N \leq 3000
* 1 \leq M \leq 3000

Input

Input is given from Standard Input in the following format:


N M


Output

Print the count of the different possible sequences of colors of 2 \times M bricks that will be stacked, modulo 10^9+7.

Examples

Input

2 3


Output

56


Input

1000 10


Output

1048576


Input

1000 3000


Output

693347555
#include <cstdio>
#include <set>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;
const int N = 3005;

int n,m;
int dp[N][N][2];

int f(int i,int crv,int nula){
    if(dp[i][crv][nula] != -1) return dp[i][crv][nula];
    if(crv == 0) nula = 1;
	if(i == m) {
        return nula;
	}
	int plv = n - crv;
	int ret = 0;
	if(crv > 0){
		ret = (ret+ (f(i + 1,crv - 1, nula | (crv -1 == 0)) + f(i + 1,crv, nula | (crv - 1 == 0))) % MOD ) % MOD;
	}
	if(plv > 0){
		ret = (ret + (f(i + 1,crv + 1,  nula) + f(i + 1,crv,nula))% MOD ) % MOD;
	}
	return dp[i][crv][nula] = ret;
}

int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&m);
    int sol = 0;
    for(int i = 0;i<=n;i++){
        sol = (sol + f(0,i,0)) % MOD;
    }
    printf("%d\n",sol);
}
