Tổ hợp xúc xắc

Trong một buổi làm việc về kế toán, FullHouse Dev được giao một bài toán thú vị về xác suất. Họ cần tính toán số cách có thể để đạt được một tổng nhất định bằng cách tung xúc xắc nhiều lần.

Bài toán

FullHouse Dev cần đếm số cách có thể để tạo ra tổng \(n\) bằng cách tung một con xúc xắc một hoặc nhiều lần. Mỗi lần tung sẽ cho một kết quả từ 1 đến 6.

INPUT FORMAT:

• Dòng duy nhất chứa một số nguyên \(n\).

OUTPUT FORMAT:

• In ra số cách có thể tạo ra tổng \(n\) theo modulo \(10^9+7\).

Ràng buộc:

• \(1 \leq n \leq 10^6\)

Ví dụ

INPUT

3

OUTPUT

4

Giải thích

Với \(n = 3\), có 4 cách để tạo ra tổng này:

• 1 + 1 + 1
• 1 + 2
• 2 + 1
• 3