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
Bình luận
Bài tương tự: https://oj.vnoi.info/problem/fc137_rop
Mong AD kiểm tra lại test được không ạ 1 code nộp 2 lần nhưng lại WA khác nhau ạ
mình nộp vẫn bth nhé, bạn xem lại code bản thân ntn