Đếm số cách quay xí ngầu nhiều lần để được tổng các nút là \(n\). Lưu ý: xí ngầu có 6 mặt.

Ví dụ: \(n=3\) có 4 cách quay:

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

Input

• Một số nguyên dương \(n\)

Output

• Số cách, theo modulo \(10^9+7\)

Điều kiện

• \(1 \le n \le 10^{9}\)

Sample Input 1

3

Sample Output 1

4