【题目描述】

出个题就好了.这就是出题人没有写题目背景的原因.

你在平面直角坐标系上.

你一开始位于(0,0).

每次可以在上/下/左/右四个方向中选一个走一步.

即:从(x,y)走到(x,y+1),(x,y-1),(x-1,y),(x+1,y)四个位置中的其中一个.

允许你走的步数已经确定为n.现在你想走n步之后回到(0,0).但这太简单了.你希望知道有多少种不同的方案能够使你在n步之后回到(0,0).当且仅当两种方案至少有一步走的方向不同,这两种方案被认为是不同的.

答案可能很大所以只需要输出答案对10^9+7取模后的结果.(10^9+7=1000000007,1和7之间有8个0)

这还是太简单了,所以你给能够到达的格点加上了一些限制.一共有三种限制,加上没有限制的情况,一共有四种情况,用0,1,2,3标号:

0.没有任何限制,可以到达坐标系上所有的点,即能到达的点集为{(x,y)|x,y为整数}

1.只允许到达x轴非负半轴上的点.即能到达的点集为{(x,y)|x为非负数,y=0}

2.只允许到达坐标轴上的点.即能到达的点集为{(x,y)|x=0或y=0}

3.只允许到达x轴非负半轴上的点,y轴非负半轴上的点以及第1象限的点.即能到达的点集为{(x,y)|x>=0,y>=0}

【输入格式】

一行两个整数(空格隔开)n和typ,分别表示你必须恰好走的步数和限制的种类.typ的含义见【题目描述】.

【输出格式】

一行一个整数ans,表示不同的方案数对10^9+7取模后的结果.

【样例输入0】

100 0

【样例输出0】

383726909

【样例输入1】

100 1

【样例输出1】

265470434

【样例输入2】

100 2

【样例输出2】

376611634

【样例输入3】

100 3

【样例输出3】

627595255

【数据范围】

10%的数据,typ=0,n<=100

10%的数据,typ=0,n<=1000

5%的数据, typ=0,n<=100000

10%的数据,typ=1,n<=100

10%的数据,typ=1,n<=1000

5%的数据, typ=1,n<=100000

10%的数据,typ=2,n<=100

15%的数据,typ=2,n<=1000

10%的数据,typ=3,n<=100

10%的数据,typ=3,n<=1000

5%的数据, typ=3,n<=100000

以上11部分数据没有交集.

100%的数据,保证n为偶数,2<=n<=100000,0<=typ<=3.