Cho số nguyên dương n. Đếm các số nguyên dương có đúng n chữ số trong hệ thập phân, chia hết cho 13, đồng thời không chứa chữ số 1 và 3. Biểu diễn thập phân không có chữ số 0 ở đầu.

Dữ liệu vào

Một số nguyên n (1 ≤ n ≤ 10⁵).

Kết quả

Số lượng tìm được, lấy dư cho 10⁹ + 7.

Ví dụ

Input

2

Output

4

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.