又到了面试的时节，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*1+6*3+9*3+12*1=60

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

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

注意（t^k） % 542！=t^（k % 542）！！