Nhiệm vụ của bạn là đếm số cách khác nhau để tạo ra 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 tạo 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

Một dòng chứa một số nguyên N (1 <= N <= 10^6).

Output

In ra số cách tìm được modulo 10^9 + 7.

Examples

input
3
output
4

input
2
output
2

input
5
output
16