Limak, như bao người khác, lúc vui lúc buồn. Cảm xúc của anh thay đổi khi anh đọc một chuỗi gồm các chữ cái in hoa tiếng Anh.

• Chữ S hoặc D luôn làm Limak buồn, bất kể trước đó anh đang vui hay buồn.
• Chữ H làm Limak vui.
• Các nguyên âm A, E, I, O, U làm đảo ngược cảm xúc hiện tại (vui \(\leftrightarrow\) buồn).
• Những chữ cái còn lại không làm thay đổi cảm xúc.
  Ban đầu Limak đang vui. Với mọi xâu độ dài \(n\) trên bảng chữ cái 26 ký tự in hoa, hãy đếm số xâu mà sau khi đọc xong Limak vẫn vui. In kết quả theo 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\).

1

19

2

403

11

145418665