Matrix Exponentiation - String Mood

View as PDF
Submit solution
Points: 0.50
Time limit: 0.25s
Memory limit: 256M
Input: stdin
Output: stdout
Suggester:
chrome
Problem source:
Errichto Matrix Exponentiation
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Limak, 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 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 Limak đ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à Limak sẽ vui sau khi đọc xâu đó. In ra đáp án modulo ~10^9+7~

Input

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

Output

In ra đáp án modulo ~10^9+7~.

Sample 1

Input
1
Output
19
Giải thích

Có tất cả ~19~ xâu có độ dài ~n=1~ làm Limak 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 Limak thấy buồn.

Sample 2

Input
2
Output
403
Giải thích

Với ~n=2~, có ~403~ xâu làm Limak thấy vui. Xâu AO là một ví dụ vì Limak sẽ thay đổi cảm xúc hai lần. Tương tự, xâu SO cũng được tính vì làm Limak buồn rồi sau đó vui trở lại với chữ O.

Sample 3

Input
11
Output
145418665

Comments

Please read the guidelines before commenting.