问题 H: 进阶杨辉三角
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：683
解决：181
题目描述
杨辉三角在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。 在欧洲，帕斯卡（1623—-1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。 帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。
如你所知，杨辉三角是这样一个三角形，下层的每一个数都是上层相邻两个数之和。然而，粗心的小F不小心把杨辉三角打翻了，于是它变成了这样一个数组：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ……
小F不知道怎么恢复杨辉三角，于是来求助你，请聪明的你编写程序，求出这个数组的第k个数是多少（mod 1e9+7），数组下标从 1 开始。
如你所知，杨辉三角是这样一个三角形，下层的每一个数都是上层相邻两个数之和。然而，粗心的小F不小心把杨辉三角打翻了，于是它变成了这样一个数组：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ……
小F不知道怎么恢复杨辉三角，于是来求助你，请聪明的你编写程序，求出这个数组的第k个数是多少（mod 1e9+7），数组下标从 1 开始。
输入
第一行为 t，代表有t组测试数据，t <= 10000
之后 t 行，每行一个数k，表示你要求的杨辉三角数组中第k个数，1 <= k <= 50000
之后 t 行，每行一个数k，表示你要求的杨辉三角数组中第k个数，1 <= k <= 50000
输出
输出共 t 行，每行一个数，表示 杨辉三角数组中第k个数（ mod 1e9+7 ）
样例输入 复制
5
1
2
3
4
5样例输出 复制
1
1
1
1
2