Description

函数f(n,k)定义如下：

int f(int i,int k)

{

Return i^4 * k^i;

}

给定常数k，数列A定义为A[i]=f(i,k);

对于特定的n，求数列A的前n项和Sn=A[1]+A[2]+A[3]+…+A[n];

注意 结果取模1000007！！！

Input

输入包含多组数据，每组数据包含一行两个整数n和k(1<=n<=10^9,k<1000007)。处理到文件结束。

Output

每个输入对应一行输出结果。

Sample

Input

1 0
2 3
3 4
181 435

Output

0
147
5444
296757

Source: zjut_DD