Bạn được cho một số nguyên \(N\). Tìm số lượng chuỗi có độ dài \(N\) thỏa mãn các điều kiện sau, modulo \(10^9 + 7\):

• Chuỗi không chứa ký tự nào ngoài \(A, C, G\) và \(T\).
• Chuỗi không chứa \(AGC\) là chuỗi con.
• Điều kiện trên không bị vi phạm khi hoán đổi hai ký tự liền kề một lần.

Ghi chú

Một chuỗi con của một chuỗi \(T\) là một chuỗi thu được bằng cách loại bỏ không hoặc nhiều ký tự từ đầu và cuối của \(T\).

Ràng buộc

• \(3 \leq N \leq 100\)

INPUT FORMAT

• Đầu vào được cung cấp từ Standard Input theo định dạng sau:

  N

OUTPUT FORMAT

• In ra số lượng chuỗi có độ dài \(N\) thỏa mãn các điều kiện, modulo \(10^9 + 7\).

Ví dụ:

Input

3

Output

61

Có \(4^3 = 64\) chuỗi có độ dài \(3\) không chứa ký tự nào ngoài \(A, C, G\) và \(T\). Trong số đó, chỉ có \(AGC, ACG\) và \(GAC\) vi phạm điều kiện, do đó kết quả là \(64 - 3 = 61\).

Input

4

Output

230

Giải thích ví dụ mẫu

Ví dụ:

• Input:

  3

• Giải thích:

  • Có tổng cộng 64 chuỗi độ dài 3 từ các ký tự A, C, G, T. Ba chuỗi "AGC", "ACG", "GAC" vi phạm điều kiện, nên số chuỗi hợp lệ là 64 - 3 = 61.

Ví dụ:

• Input:

  4

• Giải thích:

  • Có tổng cộng 256 chuỗi độ dài 4. Số chuỗi vi phạm điều kiện là 26, nên kết quả là 256 - 26 = 230.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House