零崎的人间冒险Ⅲ

题目描述

不打麻将的零崎特别的无聊，所以他又四处乱逛了。 四处乱逛的无聊零崎遇到了另一个特别无聊的人，因为这个人竟然在无聊的算各种一元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吗？