Trong giờ học về dãy số, cô giáo đã đưa ra một dãy số có quy luật như sau:

~U_0 = -1, U_1 = 3, U_{n+1} = 5*U_n - 6*U_{n-1}~

Với một số n cho trước, nhiệm vụ của bạn là đưa ra kết quả ~U_n \% (1e^9 + 7)~

Input

Một dòng duy nhất gồm số nguyên dương n ~(0 \leq n \leq 10^{11})~

Output

Một số nguyên duy nhất là kết quả ~U_n \% (1e^9 + 7)~

Sample

Input #1

1

Output #1

3

Input #2

2

Output #2

21

Problem source: CLB Lập Trình PTIT