Mảnh ghép
Đề bài
Mô tả
Bạn được cho mảnh ghép kích thước (trò ghép hình một chiều). Mỗi mảnh gồm ô vuông xếp thành một hàng ngang.
Mỗi mảnh có hai đầu (đầu trái và đầu phải), mỗi đầu thuộc một trong ba loại "in", "out" hoặc "none":
- Loại "in" nghĩa là đường viền của đầu đó lõm vào.
- Loại "out" nghĩa là đường viền lồi ra.
- Loại "none" nghĩa là đường viền thẳng.
Ví dụ, một mảnh có hai đầu "out" là mảnh có cả hai đầu lồi; một mảnh có đầu trái "in" và đầu phải "none" là mảnh lõm ở bên trái và thẳng ở bên phải.
Có một số quy tắc:
- Không được lật các mảnh, nói cách khác, không được đổi chỗ đầu trái và đầu phải của bất kỳ mảnh nào.
- Một đầu "in" có thể nối với một đầu "out" bất kỳ và ngược lại.
- Không được nối vào một đầu loại "none".
Bạn cần nối một số mảnh (có thể chỉ một mảnh) lần lượt nối tiếp nhau, đầu phải của mảnh trước nối với đầu trái của mảnh sau, để được một mảnh lớn có độ dài . Cả hai đầu của mảnh lớn này đều phải là loại "none". Hãy đếm xem có bao nhiêu tập mảnh khác nhau mà có thể dùng tất cả các mảnh trong tập để ghép thành mảnh lớn độ dài . Các mảnh được phân biệt theo thứ tự trong dữ liệu vào, kể cả khi chúng giống hệt nhau. Lưu ý: cần đếm số tập mảnh, không phải số cách ghép. Vì kết quả có thể rất lớn, hãy in ra kết quả modulo .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : số mảnh ghép và độ dài mong muốn của mảnh lớn.
- dòng tiếp theo mô tả các mảnh. Dòng thứ gồm một số nguyên và hai xâu , : độ dài của mảnh, loại đầu trái và loại đầu phải. Xâu "in" chỉ đầu lõm, "out" chỉ đầu lồi, "none" chỉ đầu thẳng.
Dữ liệu ra
In ra một số nguyên duy nhất là số tập mảnh có thể dùng để ghép thành mảnh lớn mong muốn, modulo .
Ràng buộc
- , .
- .
- "in", "out", "none".
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 10 1 out out 6 none in 10 none none 4 out none 3 in none |
3 | Ba tập hợp lệ: chỉ mảnh 3 (độ dài 10); mảnh 2 nối với mảnh 4 (đầu "in" của mảnh 2 nối với đầu "out" của mảnh 4, độ dài ); mảnh 2, mảnh 1, mảnh 5 theo thứ tự đó (độ dài ). |
| 4 5 1 none out 1 in out 2 in out 1 in none |
1 | Chỉ có tập gồm cả bốn mảnh, ghép theo thứ tự 1, 2, 3, 4 (hoặc 1, 3, 2, 4). |
Bình luận