Cho hai số nguyên n và k tìm \((Z_n + Z_{n-1} - 2Z_{n-2})\) \(mod\) \(10000007\), trong đó \(Z_n\) = \(S_n + P_n\) và \(S_n\) = \(1^k + 2^k + 3^k + … + n^k\) và \(P_n = 1^1 + 2^2 + 3^3 + … +n^n.\)

INPUT FORMAT

Có nhiều testcase \((\leq 10000)\). Trong test, hai số nguyên dương \(n\) \((1 < n < 200000000)\) và \(k\) \((0 < k < 1000000)\) được phân tách bằng dấu cách.

Đối với trường hợp thử nghiệm cuối cùng \(n\) và \(k\) được là \(0\) \(0\), không cần xử lý.

OUTPUT FORMAT

Đối với mỗi trường hợp, hãy in giá trị được yêu cầu ở trên một dòng.

Ví dụ 1:

Input

10 3
9 31
83 17
5 2
0 0

Ouput

4835897
2118762
2285275
3694

Giải thích ví dụ mẫu:

Ví dụ 1:

• Giải thích: Tính \((Z_{10} + Z_{9} - 2Z_{8}) \mod 10000007\), với \(Z_n = S_n + P_n\), \(S_n\) là tổng các số \(i^k\) từ \(i=1\) đến \(n\) và \(P_n\) là tổng các số \(i^i\) từ \(i=1\) đến \(n\).

Ví dụ 2:

• Giải thích: Tính \((Z_9 + Z_8 - 2Z_7) \mod 10000007\), với \(Z_n\) tính tương tự như trên.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House