3006. 计算多项式的系数 II

单测试点时限: 5.0 秒

内存限制: 256 MB

给定一个多项式 (ax+by)k,计算多项式展开后 xnym 项的系数。

输入

第 1 行:一个整数 T (1≤T≤100000)为问题数。

接下来共 T 行。每行 5 个整数,分别为 a,b,k,n,m,整数之间由一个空格分隔。

0≤k≤1,000,000,0≤n,m≤k,且 n+m=k,0≤a,b≤10^9。

输出

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。

然后对应每个问题在一行中输出一个整数,表示所求的系数(这个系数可能很大,输出对 1000000007 取模后的值)。

样例

Input
3
1 1 3 1 2
235823 382573 999 111 888
681692776 714636914 287579 7786 279793
Output
case #0:
3
case #1:
939550478
case #2:
388290460

52 人解决,119 已尝试。

106 份提交通过,共有 414 份提交。

7.5 EMB 奖励。

创建: 5 年,3 月前.

修改: 1 年,3 月前.

最后提交: 1 周,1 天前.

来源: 2013年编程实践课程师范班第3次上机考试(改编)