主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 B: A Simple Math Problem 3

问题 B: A Simple Math Problem 3

时间限制: 2 Sec  内存限制: 128 MB
提交: 447  解决: 87
[提交][状态][讨论版]

题目描述

又到了面试的时节,pengbeidada今天该面试阿讯公司了,面试官觉得数理基础特别重要,所以给他写下了一个数列:

a(n)=sum((p+i*d)*C(n,i)) % 542. (0<=i<=n,C(n,m)表示从n个物品中取m个物品的组合数)。

面试官要求dada算出这个的第n(2<=n<=2*1e7)项的值说这个不是很简单啊,但是突然发现电脑卡了,所以向你求助这个问题。

输入

输入第一行为数据组数T(0<T<5*1e5),有多组数据,每组一行,分别为p d n(abs(p)<=1e9,abs(d)<=1e9).

保证p、d都是正整数!!!

输出

对于每组数据,输出相应的数列第n项的值。

样例输入

3
4 4 4
2 2 2
3 3 3

样例输出

192
16
60

提示

第三组样例:3*1+6*3+9*3+12*1=60


第二组样例:2*1+4*2+6*1=16


请大家不要再尝试暴力!!


注意(t^k) % 542!=t^(k % 542)!!


[提交][状态][讨论版]