Description

已知函数f(x)=n^x;要求给出前m项的和，即f(1)+f(2)+……+f(m);

Input

输入n,m;( 1<=n<=100000,1<=m<=1000); 0 0 表示输入结束，并且对0 0 不用进行处理。

Output

输出f(x)前m项的和。(结果可能很大，对结果mod 10000即可)

Sample

Input

2 3
4 2
0 0

Output

14
20

Source: zhuzewei