Các chú nhóc XI TRUM ở Vương quốc Happy land có một thói quen là khi gặp nhau các chú thường đọc tên của nhau (bằng cách đánh vần từng chữ cái của tên), sau khi đọc tên của một ai đó, tâm trạng của người đọc sẽ hạnh phúc hay không hạnh phúc phụ thuộc vào tên mà XI TRUM theo quy tắc sau đây:

• Nếu tên gọi có chứa các chữ cái ~'S','D'~ sau khi đánh vần chữ cái này, tâm trạng của người đọc sẽ hạnh phúc;
• Nếu tên gọi có chứa chữ cái ~'H'~ sau khi đánh vần chữ cái này, tâm trạng của người đọc sẽ không hạnh phúc;
• Nếu tên gọi có chứa các chữ cái ~'A', 'E', 'I','O', 'U'~ sau khi đánh vần chữ cái này, tâm trạng của người đọc sẽ hạnh phúc chuyển thành không hạnh phúc và ngược lại. Ví dụ: với tên là ~SMMMM, DNNPPP~ là những tên mà sau khi đánh vần sẽ mang lại hạnh phúc cho XI TRUM còn tên ~HTTTTG~ sẽ mang lại tâm trạng không hạnh phúc cho XI TRUM; các tên ~SONG, EM~ sau khi đọc xong sẽ đảo ngược tâm trạng của các XITRUM.

Tâm trạng của XI TRUM khi bắt đầu ngày mới là hạnh phúc, tâm trạng hạnh phúc hay không hạnh phúc sẽ ảnh hưởng đến hiệu suất làm việc của XI TRUM là tốt hay xấu. Nên Tộc trưởng của tộc XI TRUM muốn đặt tất cả các tên của XITRUM thành tên mà sau khi đọc tên này sẽ mang lại tâm trạng hạnh phúc cho người đọc tên đó. Trước khi chọn các tên để đặt thì tộc trưởng muốn biết với số nguyên dương ~n~ thì có bao nhiêu cái tên có ~n~ chữ cái (các chữ cái trong bảng chữ cái tiếng anh in hoa) sau khi đọc xong sẽ mang lại tâm trạng hạnh phúc cho người đọc.

Yêu cầu: Cho trước số nguyên dương ~n~, hãy giúp tộc trưởng tính xem có bao nhiêu cái tên có ~n~ chữ cái sẽ mang lại tâm trạng hạnh phúc cho người đọc tâm trạng ban đầu của người đọc là hạnh phúc.

Dữ liệu:

• Gồm một dòng duy nhất chứa một số nguyên dương ~1 \leq n \leq 10^{18}~.

Kết quả:

• Ghi một số nguyên là kết quả tìm được, do kết quả rất lớn chỉ cần đưa ra số dư khi lấy kết quả chia cho ~10^{9}+7~.

Ví dụ:

Sample Input 1

1

Sample Output 1

20

Sample Input 2

2

Sample Output 2

442

Sample Input 3

11

Sample Output 3

145418665

Giới hạn:

• Subtask 1: ~25 \%~ các test có ~n \leq 5~;
• Subtask 2: ~50 \%~ các test có ~n \leq 10^{6}~;
• Subtask 3: ~25 \%~ các test có ~n \leq 10^{18}~.