📖 Bài giảng & lời giải: đây là Bài tập 5 trong bài giảng Thuật toán qua trò chơi 5: Cờ caro trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Tic-tac-toe được chơi trên bàn $3 \times 3$: X đi trước, hai người lần lượt đánh vào một ô trống; ai có 3 quân thẳng hàng (ngang, dọc hoặc chéo) trước thì thắng và ván kết thúc ngay; nếu bàn kín mà chưa ai thắng thì ván hoà.

Cho một thế cờ hợp lệ (đạt được từ bàn trống theo đúng luật trên). Người tới lượt được xác định bởi số quân: nếu số X bằng số O thì tới lượt X, ngược lại tới lượt O. Hai người tiếp tục đánh lần lượt cho tới khi ván kết thúc. Có bao nhiêu cách chơi tiếp khác nhau? Hai cách chơi được coi là khác nhau nếu ở một bước nào đó hai cách đánh vào hai ô khác nhau. Nếu ván đã kết thúc (đã có người thắng hoặc bàn đã kín) thì đáp án là 1.

Dữ liệu vào

Gồm 3 dòng, mỗi dòng là một xâu 3 ký tự X, O, . (ô trống) mô tả thế cờ.

Kết quả

In ra số cách chơi tiếp.

Sample Input

...
...
...

Sample Output

255168