Nhiệm vụ của bạn là đếm số cách để tạo thành tổng ~n~ bằng cách gieo một con xúc xắc một hoặc nhiều lần. Mỗi lần gieo cho 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~

Dữ liệu vào

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

Kết quả

In ra số cách lấy modulo ~10^9+7~.

Giới hạn

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

Ví dụ

Input:

3

Output:

4