Tí đang đi mua đồ ở một cửa hàng mà mỗi món đồ có giá từ $1$ đến $6$ xu. Tí có đúng $n$ xu trong túi và muốn tiêu hết số xu đó bằng cách mua các món đồ. Mỗi lần mua, Tí có thể chọn mua một món với giá $1,2,3,4,5$ hoặc $6$ xu, và số lượng món thì không giới hạn.

Nhiệm vụ của bạn là giúp Tí đếm xem có bao nhiêu cách để Tí có thể sử dụng đúng $n$ xu để mua sắm, với mỗi lần mua Tí có thể chọn tiêu từ $1$ đến $6$ xu.

Ví dụ, nếu Tí có $3$ xu, thì có $4$ cách để Tí tiêu hết số tiền đó:

• Mua ba món giá 1 xu: $1+1+1$
• Mua một món giá 1 xu và một món giá 2 xu: $1+2$
• Mua một món giá 2 xu và một món giá 1 xu: $2+1$
• Mua một món giá 3 xu: $3$

Bạn hãy giúp Tí tính số cách để tiêu đúng số xu đó, và vì kết quả có thể rất lớn, hãy đưa ra số dư của kết quả khi chia cho ${10}^9+7$.

Input

• Một số nguyên $n$ là số xu mà Tí có ($1\le n\le {10}^6$)

Output

• Số cách để Tí tiêu hết đúng $n$ xu, kết quả này lấy dư cho ${10}^9+7$

Sample Test

Input 1

3

Output 1

4

Input 2

5

Output 2

16