http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2272

Description

Hedwig the hamster enjoys exploring networks of hamster tubes. Each day, Hedwig's ownerrearranges the tubes to form a new network of tubes.

One day, Hedwig awoke to find that the network of tubes had been arranged in a ladder pattern as shown below, where each junction point (An and Bn) contained a small piece of carrot (Hedwig loves carrots!). Hedwig had not yet explored the new tube network and had no idea how long it was (it may go on forever!)

avatar

Hedwig decided to make a game where given a length, figure out how many paths from the start, A0, of the given length there are using these rules: Each time a junction is reached, Hedwig eats the piece of carrot that is there. A junction can only be used if there is a piece of carrot there when Hedwig arrives.

To help Hedwig out, you will write a program which finds the number of paths from A0 of a specified length which do not hit any junction more than once. For example, all the paths of length 3 are shown below:

avatar

Input

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 800), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of one line of input. The line contains the data set number, K, followed by the length, N, (1 ≤ N ≤ 1000)of the paths to be counted.

Output

For each data set there is one line of output.

The output line consists of the data set number, K, followed by the number of paths of length N modulo 10007.

Sample Input

4
1 3
2 9
3 18
4 111

Sample Output

1 6
2 110
3 8361
4 237

Hint

Source

题目大意：给一个图，只有两行，有无限列，问你一根长度为n的线有几种画法。(不能有相交的点或线段)

思路：自己在图上画一下就就能找到规律了。对于长度为i的线，如果先往右画一格，那么剩下的部分可以完全仿照i-1的情况；如果先向下画一格则下一步必须向右画一格，那么剩下的部分可以完全仿照i-2的情况，但是当i为奇数的时候，会多1种情况，即上线对称的折返。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int sum[1005];
const int MOD=10007;
int t,n,m;

int main()
{
	sum[1]=2,sum[2]=3;
	for(int i=3;i<=1000;i++)
	{
		if(i&1)
			sum[i]=sum[i-1]+sum[i-2]+1;
		else
			sum[i]=sum[i-1]+sum[i-2];
		sum[i]%=MOD;
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		printf("%d %d\n",n,sum[m]);
	}
	return 0;
}