Matrix Exponentiation - String Mood

Xem dạng PDF

Gửi bài giải


Điểm: 0,50
Giới hạn thời gian: 0.25s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Errichto Matrix Exponentiation
Dạng bài
Ngôn ngữ cho phép
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ữ SD 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

Hãy đọc nội quy trước khi bình luận.



  • 0
    princeoftime05  đã bình luận lúc 31, Tháng 12, 2022, 15:20 chỉnh sửa

    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 ạ


    • 0
      nguyene2p  đã bình luận lúc 29, Tháng 1, 2023, 8:32

      mình nộp vẫn bth nhé, bạn xem lại code bản thân ntn