Hàm đặc biệt

View as PDF
Submit solution
All submissions
Best submissions
Time limit: 1.0s , Memory limit: 256M , Points: 30 (partial)

Khi đang chuẩn bị hành lý cho kỳ thi OLP tại Hà Nội, Kichirou vô tình làm rơi một cuốn sách toán học cũ. Từ trong sách, một mảnh giấy đã ngả màu rơi ra, trên đó có ghi: Trong cánh cửa bí mật của tri thức, chỉ những người giải được chuỗi mã hóa cổ xưa này mới có thể tìm thấy ánh sáng của tương lai. Bên dưới là một bài toán lạ lùng:

Cho một dãy số F, trong đó:

  • F[0] = 0
  • F[1] = 1
  • F[i] = \sum_{j = max(0, i - k)}^{i - 1} (F[j] + i ^ 2 - j).

Tính F[n] sau khi chia dư cho 10 ^ 9 + 7.

Một số tính chất của phép chia dư:

  • (a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m
  • (a - b) \mod m = [(a \mod m) - (b \mod m)] \mod m
  • (a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m

Input

  • Dòng duy nhất chứa hai số nguyên dương n, k. (1 \le n \le 10 ^ {12}, 1 \le k \le 10).

Output

  • Dòng duy nhất chứa kết quả là giá trị F[n] sau khi chia dư cho 10^9 + 7.

Scoring

  • Subtask 1 (40% số điểm): 1 \le n \le 20 , k \le 10.
  • Subtask 2 (30% số điểm): 1 \le n \le 3 * 10 ^ 6, k \le 10.
  • Subtask 3 (30% số điểm): 1 \le n \le 10 ^ {12}, k \le 10.

Samples

Sample Input

2 2

Sample Output

8

Comments