Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

小DS做了一个梦,他梦见自己变成了柯南T_T,他潜入了黑衣组织的基地核心,找到了破解黑衣组织的密钥!!!。
密钥的组成是很多个整数对n , m (1 <=n <= 1000 , 1 <= m <= 1000)。
DS知道把n个非负整数和为m的所有解都求出来(1+2+1,1+1+2,2+1+1算三种解),然后挑出其中非0的所有元素相乘,最后让结果对1000000007(1e9+7)取余数得到的就是黑衣组织系统的密码!!!可是正当他计算的时候,门外传来了琴酒和伏特加的脚步声。你能帮助DS求出他要的答案么。

你可能用到的一些定理和性质
欧拉定理

在数论中,欧拉定理(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则a^φ(n) ≡ 1 (mod n)。

费马小定理

a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p)

Barty-Bella大定理

没有过不了的神题,只有不勤奋的Coder!

Input

第一行是一个整数T(T <= 2000),代表桌面上的整数对数。
每组数据包含两个数字n , m 代表密钥。

Output

输出T行,每行一个整数,代表密码。
如果无解输出 "Poor Conan T_T", 不含引号

Sample Input

2
3 3
2 2

Sample Output

1728
4

Hint

对于第一组数据,3 = 0 + 1 + 2 = 0 + 2 + 1 = 1 + 0 + 2 = 1 + 2 + 0 = 2 + 1 + 0 = 2 + 0 + 1 = 1 + 1 + 1 = 3 + 0 + 0 = 0 + 3 + 0 = 0 + 0 + 3。
因此答案就是1 * 2 * 2 * 1 * 1 * 2 * 1 * 2 * 2 * 1 * 2 * 1 * 1 * 1 * 1 * 3 * 3 * 3 = 1728.
对于第二组数据, 2 = 0 + 2 = 2 + 0 = 1 + 1
因此答案就是 2 * 2 * 1 * 1 = 4.

Source

Dshawn

Manager

Information
Solved Number62
Submit Number198
Problem Tags
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel