次幂求和

输入n, k，输出1到n的k次幂之和，即$1^k + 2^k + 3^k + ... + n^k$。

结果对$10007$取模。

输入描述

一行两个整数n, k。

输出描述

一行一个整数表示答案。

样例输入

10 3

样例输出

3025

样例输入

1000000000 2

样例输出

8955

数据规模与约定

对于100%的数据，满足$1 <= n <= 1000000000, 1 <= k <= 100$。

存在$k = 1, 2, 3, 4, 5$的数据。

不要交$O(n)$的算法，一定是0分。