Cerința

Se dau n şi k numere naturale. Calculați suma \( \sum_{i=1}^{n}i^{k} \).

Date de intrare

Programul citește de la tastatură numerele naturale n şi k.

Date de ieșire

Programul va afișa pe ecran valoarea sumei \( \sum_{i=1}^{n}i^{k} \), modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 100.000 şi 1 ≤ k ≤ 1.000.000.000 pentru 70% din teste
• 1 ≤ n ≤ 1.000.000.000 şi 1 ≤ k ≤ 100.000 pentru 30% din teste

Exemplu:

Intrare

5 3

Ieșire

225

Explicație

\( \sum_{i=1}^{5}i^{3} = 1^{3}+2^{3}+3^{3}+4^{3}+5^{3} = 225\)