多项式计算器

题目描述

Magry最近想要个计算器，其功能需求如下：

给定一元n次多项式的次数n、一个x的值与查询次数t，再输入t组系数a0,a1,...,an来分别求t个一元n次多项式a0+a1x+a2x^2+……+anx^n的值。

时间很急很关键，亲们快帮他一把！

输入

多组测试数据(不超过10组)，以EOF结尾。

每组测试数据第一行为三个整数n、x、t，其中n代表一元n次多项式的次数，x代表一元n次多项式的x值，t代表t组系数。

接下来t行，每行n+1个数，依次表示一个一元n次多项式的系数a0,a1,...,an.

保证输入数据 t 均为不大于10000的正整数， n, x值及系数 a0,a1,...,an 均为不大于10000的非负数。

输出

对于每组数据，在第一个一元n次多项式计算结果输出前输出一行，Case #X:（冒号为英文引号，X代表第几组数据，如第一组为Case #1:第二组为Case #2:,...,第十组为Case #10:,以此类推）

对于每个一元n次多项式，输出一行，一个数，一元n次多项式的最终计算结果。鉴于最终结果可能较大，每个结果均对1e6+7取模。

具体参见样例。

输入样例

3 1 3
0 1 2 3
1 2 3 4
6 9 0 0
2 10 1
1 2 3

输出样例

Case #1:
6
10
15
Case #2:
321

Hint

鉴于运算过程中可能会出现超出int数据范围的情形，如会出现类似900000*10000的运算过程，请大家注意要在遵循“边加边取模，边乘边取模”的原则之上，对各种数据使用long long数据类型。