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:
  Copy

  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