Trong bài toán Tháp Hà Nội, có ~N~ đĩa theo thứ tự từ nhỏ đến lớn đang nằm ở cột ~A~ như hình bên dưới:

Cần chuyển ~N~ đĩa trên từ cột ~A~ sang cột ~B~ (lấy cột ~C~ làm cột trung gian) theo quy tắc:

• Mỗi lần chỉ chuyển một đĩa.
• Đĩa nhỏ phải nằm trên đĩa lớn tại bất kỳ thời điểm nào trong quá trình chuyển.
• Mỗi lần chỉ được chuyển 1 tầng tháp từ một cọc sang cọc sát nó theo chiều kim đồng hồ:

Câu hỏi như sau: Để chuyển ~N~ đĩa từ cột ~A~ sang cột ~B~ theo quy tắc trên, thì phải chuyển ít nhất bao nhiêu lần?

Input

Gồm ~1~ dòng duy nhất chứa số nguyên dương ~N~ là số đĩa ở cột ~A (1 \le N \le 10^4)~

Output

Gồm ~1~ dòng chứa duy nhất ~1~ số nguyên dương là kết quả của bài toán trên.

Đáp án cần in ra có thể rất lớn, hãy in ra đáp án sau khi chia dư cho ~10^9 + 7~

Sample

Input #1

3

Output #1

15

Input #2

15

Output #2

2781183

Hint

• Với #1 ta có các bước xếp đĩa sau:

~01~ ~A - B~

~02~ ~B - C~

~03~ ~A - B~

~04~ ~C - A~

~05~ ~B - C~

~06~ ~A - B~

~07~ ~B - C~

~08~ ~A - B~

~09~ ~C - A~

~10~ ~A - B~

~11~ ~C - A~

~12~ ~B - C~

~13~ ~A - B~

~14~ ~C - A~

~15~ ~A - B~

Tổng cộng có ít nhất ~15~ lần xếp.