Hạo, như bao người khác, lúc vui lúc buồn. Cảm xúc của anh ấy thay đổi (hoặc không thay đổi) khi anh ấy đọc một từ tiếng Anh với các chữ cái in hoa. Chữ \(S\) và \(D\) luôn làm anh ấy buồn, trong khi \(H\) luôn làm anh ấy vui và các nguyên âm \(A,E,I,O,U\) làm đảo ngược cảm xúc của anh ấy (vui thành buồn hoặc ngược lại). Những chữ còn lại không làm thay đổi cảm xúc của anh ấy.

Hiện tại Hạo đang vui. Trong tất cả \(26^n\) xâu với \(n\) chữ cái tiếng anh in hoa, đếm số xâu mà Hạo sẽ vui sau khi đọc xâu đó. In ra đáp án modulo \(10^9+7\)

Dữ liệu vào

• Một số nguyên dương \(n\) \((1 \le n \le 10^{18})\)

Dữ liệu ra

• In ra đáp án modulo \(10^9+7\)

Input 1

1

Output 1

19

Giải thích

Có tất cả \(19\) xâu có độ dài \(n=1\) làm Hạo cảm thấy vui là: \(B, C, F,G, H, J, K, L, M, N, P, Q, R, T, V, W, X, Y, Z\). Các xâu có nguyên âm và chữ \(S\) hoặc \(D\) sẽ làm Hạo thấy buồn.

Input 2

2

Output 2

403

Input 3

11

Output 3

145418665