INS14H - Virus Revisited
题意翻译
• 在一个 **n** 维无限空间中，一开始原点处有一个细胞。
• 细胞每秒都会增殖，每个原有细胞在增值后都会消亡，在与它曼哈顿距离恰为 **1** 的所有位置都会新增一个细胞。
• 求 **T** 秒后，原点处会有多少细胞，答案 %(1e9+7)。
• **Q** 组询问。**Q**≤20000 **n**≤100 **T**≤200。
题目描述
Due to the failed experiment in the laboratory of our scientist Digo, a new universe of N dimensions is created with one single virus at origin at time T=0.
Each point in this new universe can be represented by a linear array of indices (c1, c2, c3, ... cn) where ci represents the i th coordinate. In this new universe we are interested in only integer points i.e, points with integer coordinates. Two points (a1, a2, ...an), (b1, b2, ...bn) are adjacent to each other if sum of abs(ai - bi) for all i is equal to 1 (abs() is the absolute value function). If observed carefully one can observe that there are 2\*N adjacent points for every point in the universe. Origin is (0, 0, ...n times).
The virus reproduces very rapidly. After every second it gives birth to 2\*N identical new viruses of its kind and dies. As the newly born viruses are born, each of them moves to a distinct point, each of which are adjacent to the point at which the parent was present. New Viruses reproduce at their respective points and this procedure goes on. As the viruses are very small, any number of viruses can stay at a single point.
Now Our Scientist Digo has Q queries. In each query he gives you two integers N and T, and you need to tell him how many viruses are present at the origin in N dimension universe at the end of T seconds.
As the Output can be huge print each output modulo (10^9 + 7).
Input Format:
First line contains a single integer Q representing the number of queries.
Q lines follow with two space separated integers N and T in each line. N, T have their respective meanings mentioned in the problem statement.
Output Format:
Print a single integer for every query in a separate line.
Constraints :
1 <= Q <= 20000
1 <= N <= 100
1 <= T <= 200
Sample Input :
3
1 2
2 3
3 2
Sample Output:
2
0
6