零崎的人间冒险Ⅲ

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 378 总提交人数: 435

题目描述

不打麻将的零崎特别的无聊,所以他又四处乱逛了。 四处乱逛的无聊零崎遇到了另一个特别无聊的人,因为这个人竟然在无聊的算各种一元n次多项式a0+a1x+a2x^2+……+anx^n!这个无聊的人算的实在太慢了令零崎忍不住想开启嘲讽模式,所以现在,快来给零崎搞一个能快速计算多项式的东西吧。(其实可能也不用特别快

输入

多组输入数据。 每组数据以多项式次数n开始,下一个数字为变量x,之后n+1个数字为系数a0……an。输入数据保证在int范围内

输出

每行一个结果,也许n特别大所以最后结果还是对1e6+7求模吧……

输入样例

1 2 1 2  
3 2 1 2 3 4

输出样例

5
49

Hint

你听说过上古卷轴吗?你听说过彩虹小马吗?你听说过Horner Rule吗?