Xét một hệ thống biến đổi chuỗi ký tự chỉ bao gồm hai loại ký tự là 'A' và 'B'. Ban đầu (tại bước 0), ta có một chuỗi chỉ chứa duy nhất một ký tự 'A'.
Tại mỗi bước biến đổi tiếp theo, các ký tự trong chuỗi sẽ đồng loạt thay đổi theo quy tắc sau:
- Mỗi ký tự 'A' sẽ được thay thế bằng chuỗi con "AAAB".
- Mỗi ký tự 'B' sẽ được thay thế bằng chuỗi con "BBBA".
Ví dụ, sau 2 bước ra có:
- Bước 0: "A"
- Bước 1: "AAAB" (Ký tự 'A' ban đầu biến thành "AAAB")
- Bước 2: "AAABAAABAAABBBBA" (3 ký tự 'A' đầu tiên mỗi ký tự biến thành "AAAB", ký tự 'B' cuối cùng biến thành "BBBA").
Hãy tính số lượng ký tự 'A' xuất hiện trong chuỗi sau bước biến đổi.
Dữ liệu:
- Dòng đầu tiên chứa một số nguyên () — số bước biến đổi.
Kết quả:
- In ra một số nguyên duy nhất — phần dư của phép chia số lượng ký tự 'A' sau bước cho ().
Ví dụ:
Dữ liệu:
Kết quả:
Dữ liệu:
Kết quả:
Giới hạn:
-
SubtaskSubtask #1 (20% số điểm): .
-
SubtaskSubtask #2 (40% số điểm): .
-
SubtaskSubtask #3 (40% số điểm): .
