malego290704 đang ngủ say sau nhiều đêm thức trăng chuẩn bị cho April Fools.

Hãy đếm số giấc mơ của anh ấy!!!

Input

• Gồm 1 số nguyên dương \(N (N \le 10^{12})\)

Output

• Gồm 1 số là kết quả của bài toán \((\mod 10^9+7)\).

Example

3

2

6

4