Bài toán: Đếm số cách tạo tổng ~ n ~ bằng cách tung xúc xắc

Đề bài

Nhiệm vụ của bạn là đếm số cách để tạo ra tổng ~ n ~ bằng cách tung một xúc xắc một hoặc nhiều lần. Mỗi lần tung xúc xắc có thể cho ra kết quả từ 1 đến 6.

Ví dụ, nếu ~ n = 3 ~, có 4 cách:

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

Input

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

Output

• In ra số cách modulo ~ 10^9 + 7 ~.

Ràng buộc

• ~ 1 \leq n \leq 10^6 ~

Ví dụ

Input:

3

Output:

4