Jessie được cô giáo cho một hình tam giác đều. Cô giáo mô tả cho Jessie các thao tác trong một phép biến đổi hình như sau:

• Với mỗi hình tam giác trong hình, xác định ~3~ điểm là trung điểm của ~3~ cạnh tam giác.

• Nối các cặp trung điểm trong một hình tam giác đôi một lại với nhau.

Cô giáo đố Jessie rằng, sau ~n~ thao tác, hình sẽ có bao nhiêu điểm? Do Jessie không có thời gian để vẽ hình và đếm, nên bạn hãy lập trình để tính số điểm trên hình giúp Jessie nhé!

Input

Gồm một dòng duy nhất ghi số nguyên ~n~ - số phép biến đổi thực hiện lên hình.

Output

In ra trên một dòng duy nhất một số nguyên - số lượng điểm trên hình sau ~n~ phép biến đổi. Do kết quả có thể rất lớn nên hãy in ra phần dư của đáp án khi chia cho ~10^9+7~.

Scoring

• Subtask #1 (~60\%~): ~0 \le n \le 30~.
• Subtask #2 (~20\%~): ~30 < n \le 10^5~
• Subtask #3 (~20\%~): ~10^5 < n \le 10^{18}~.

Sample Input 1

2

Sample Output 1

15

Sample Input 2

10

Sample Output 2

525825

Notes

Ở ví dụ đầu tiên, sau ~2~ phép biến đổi, ta được một hình có ~15~ điểm như sau: