#1607. Đếm dãy số (SEQCONST)

Cho một tập hợp các giá trị .

Nhiệm vụ của bạn là đếm số lượng dãy số nguyên bao gồm phần tử thỏa mãn tất cả các điều kiện sau:

1. Mọi phần tử của dãy số đều thuộc tập hợp ().
2. Phần tử đầu tiên và phần tử cuối cùng của dãy số đều có giá trị là 4 ( và ).
3. Hai phần tử liền kề bất kỳ trong dãy phải có giá trị khác nhau ( với mọi ).

Hãy tính số lượng dãy số thỏa mãn các điều kiện trên. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ().

Dữ liệu:

• Dòng đầu tiên chứa duy nhất số nguyên () — tham số xác định độ dài của dãy số (số lượng cặp phần tử liền kề).

Kết quả:

• In ra duy nhất một số nguyên — số lượng dãy số thỏa mãn yêu cầu theo modulo ().

Ví dụ:

Dữ liệu:

2

Kết quả:

3

Dữ liệu:

4

Kết quả:

21

Giải thích: Trong ví dụ đầu tiên với , dãy số có dạng . Ta luôn có . Điều kiện buộc phải khác 4. Các dãy số thỏa mãn là:

Tổng cộng có 3 dãy số.

Giới hạn:

• Subtask #1 (20% số điểm): .

• Subtask #2 (40% số điểm): .

• Subtask #3 (40% số điểm): .