3006. 计算多项式的系数 II

Time limit per test: 5.0 seconds

Memory limit: 256 megabytes

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

Input

第 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。

Output

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

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

Examples

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 Solved out of 118 users tried.

106 Accepted out of 412 tried.

5.3 EMB will be rewarded for solving this problem.

Created: 4 years, 11 months ago.

Updated: 11 months, 3 weeks ago.

Latest Submission: 1 month, 3 weeks ago.

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

Problem Tags