Một số được gọi là số xinh đẹp nếu các chữ số của nó nằm trong tập ~{1, 3, 0, 2}~

Yêu cầu: Đếm số lượng số xinh đẹp có số chữ số bằng ~n~

Input

~1~ dòng duy nhất là số nguyên ~n~

Output

Yêu cầu của bài toán (Phần dư khi chia cho ~10^9 + 7~)

Giới hạn

• ~2/16~ test có ~n \le 20~
• ~10/16~ test có ~n \le 10^5~
• ~4/16~ test có ~n \le 10^{15}~

Ví dụ

Sample input

2

Sample output

12

Giải thích ví dụ

~12~ số xinh đẹp có số chữ số bằng ~2~ : ~10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33~