Tổng Các Lũy Thừa · canuc80k7103

Cho hai số nguyên $n$ và $k$ . Hãy tính

1^{k} + 2^{k} + \dots + n^{k}

lấy dư theo $1000000007$ .

Khi $k = 0$ , mỗi số hạng $i^{0}$ với $1 \leq i \leq n$ được hiểu là $1$ .

Test 1

Input

4 1

Output

Giải thích: Tổng cần tính là $1 + 2 + 3 + 4 = 10$ .

Test 2

Input

5 0

Output

Giải thích: Có năm số hạng và mỗi số hạng đều bằng $1$ khi số mũ bằng $0$ .

Ý tưởng: Đặt S(x)=1^k+2^k+...+x^k và S(0)=0. Ta có
Ý tưởng: [ S(x)-S(x-1)=x^k. ]
Ý tưởng: Vì sai phân của S là đa thức bậc k, S là đa thức bậc không quá k+1. Do đó chỉ cần tính S(0),S(1),...,S(k+1) rồi nội suy tại x=n.
Ý tưởng: Các nút là những số nguyên liên tiếp. Ta chuẩn bị tích tiền tố, tích hậu tố, giai thừa và nghịch đảo giai thừa để tính toàn bộ công thức Lagrange trong O(k) sau khi đã dựng bảng giá trị. Mỗi i^k được tính bằng lũy thừa nhanh.
Ý tưởng: Trường hợp k=0 không cần tách riêng: S có bậc 1, và hai giá trị tại 0,1 đã đủ xác định S(n)=n.
Ý tưởng: Độ phức tạp là O(k log k) thời gian và O(k) bộ nhớ.