Cách đây ít năm Tichpx mua được một miếng đất hình chữ nhật trên sao Hỏa có chu vi bằng 8 đơn vị độ dài và diện tích bằng 1 đơn vị diện tích. Hôm qua ngày 20/10/2000 là ngày tận thế của sao Hỏa đã xẩy ra một vụ nổ khủng khiếp trên sao Hỏa may mắn thay sao hỏa đang từ hình cầu chỉ biến dạng thành hình elip. Mảnh đất hình chữ nhật của Tichpx trên sao hỏa đã mua cũng biến dạng nhưng vẫn là hình chữ nhật chỉ có điều chiều dài và chiều rộng thay đổi từ mỗi chiều lũy thừa lên n lần. Thực ra thì diện tích hình chữ nhật vẫn là 1 đơn vị diện tích nhưng chu vi đã thay đổi đến nỗi Tichpx không thể tưởng tượng nổi.

Bạn hãy lập trình nhập vào số nguyên dương n là số lần lũy thừa của chiều dài và chiều rộng bị biến đổi, tính chu vi hình chữ nhật mới biết rằng nó là một số nguyên dương, do kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho \(10^9+7\)

Input

Một số nguyên dương n là số lần lũy thừa mỗi chiều \((1<= n <=10^9)\) (50% số test \(n <=10^6\))

Output

Phần dư của chu vi mảnh đất của Tichpx sau khi bị biến đổi chia cho \(10^9+7\)

Ví dụ 1:

Input

2

Output

28

Ví dụ 2:

Input

3

Output

104

Ví dụ 3:

Input

100

Output

323654813