Các số trong Hệ Thập Lục Phân được biểu diễn bởi các ký tự từ 0 đến 9 và từ A đến F.

Một số trong Hệ Thập Lục Phân được coi có độ dài là \(n\) nếu nó được biểu diễn bởi \(n\) ký tự nhưng không tính số 0 ở đầu.

Ví dụ:

• 3090AF4 là số thập lục phân có độ dài là \(7\)
• A000 là số thập lục phân có độ dài là \(4\)
• 003AF là số thập lục phân có độ dài là \(3\) (vì không tính số 0 ở đầu)

Bài toán đặt ra là có bao nhiêu số thập lục phân có độ dài không quá \(n\) mà khi biểu diễn thì không có 2 số liền kề nhau.

Ví dụ:

• 3AA0AF4 là số thập lục phân không có 2 số liền kề
• 3AA00AF4 là số thập lục phân có 2 số liền kề
• 43432AG là số thập lục phân có 2 số liền kề

Input

• Một số nguyên dương \(n\) (\(n \leq 10^5\))

Output

• Một số nguyên duy nhất là số lượng số thập lục phân thỏa mãn đề bài, lấy phần dư cho \(10^9 + 7\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 5\)
• Subtask \(2\) (\(80\%\) số điểm): \(n \leq 10^5\)

Example

2

156

10101

778978905