Đồ chơi XYZ

Xem dạng PDF

Gửi bài giải


Điểm: 0,86 (OI)
Giới hạn thời gian: 0.25s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
VNOI Online Informatics Olympiad '09Day 2
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mới đây hãng sản xuất đồ chơi có sáng kiến cho ra đời bộ đồ chơi XYZ "đoán hình" như sau: đồ chơi là một bảng điện tử có kích thước ~5 \times N~ điểm sáng để giúp trẻ phân biệt được hai loại hình có kích thước ~5 \times L~ ~(L \leq N)~.

Ví dụ:

image

Hình trên: Bảng điện tử có kích thức ~5 \times 8~ ~(N = 8)~

image

Hình trên: Loại hình ~1~

image

Hình trên: Loại hình ~2~

~2~ hình trên: Hai loại hình kích thước ~5 \times 3~ ~(L = 3)~

Bảng điện tử hiển thị được gọi là chứa loại hình ~i~ ~(i = 1~ hoặc ~2)~ nếu tồn tại vị trí từ cột thứ ~k~ đến cột (k+L-1) trên bảng điện tử hiển thị đúng loại hình ~i~.

image

Hình trên: Ví dụ bảng điện tử ~5 \times 8~ chỉ chứa loại hình ~1~ (chữ ~F~ ngược ko đc tính là loại hình ~2)~

image

Hình trên: Ví dụ bảng điện tử ~5 \times 8~ chỉ chứa loại hình ~2~

image

Hình trên: Ví dụ bảng điện tử ~5 \times 8~ không chứa loại hình ~1~ và hình ~2~

image

Hình trên: Ví dụ bảng điện tử ~5 \times 8~ chứa cả loại hình ~1~ và hình ~2~

Mỗi lần bảng điện tử sẽ hiển thị và trẻ phải trả lời câu hỏi: bảng điện tử hiển thị có chứa loại hình ~1~ hay loại hình 2. Do đó, người ta muốn khảo sát xem có bao nhiêu cách hiển thị bảng điện tử khác nhau để bảng điện tử luôn chỉ chứa loại ~1~ hoặc chỉ chứa loại 2.

Yêu cầu: Cho ~N~ và hai loại hình. Gọi ~k~ là số cách hiển thị bảng điện tử khác nhau để bảng điện tử luôn chỉ chứa loại ~1~ hoặc chỉ chứa loại

  1. Hãy tính giá trị ~k~ mod 10\^6.

Input

  • Dòng đầu tiên là ~2~ số ~N~ và ~L~ ~(0 \le L \le N \le 30)~.
  • ~5~ dòng tiếp theo, mỗi dòng là một xâu ký tự độ dài ~L~ chỉ gồm ~2~ loại ký tự '.' hoặc '#" mô tả loại hình 1.
  • ~5~ dòng tiếp theo, mỗi dòng là một xâu ký tự độ dài ~L~ chỉ gồm ~2~ loại ký tự '.' hoặc '#" mô tả loại hình ~2~ (loại hình ~1~ khác loại hình ~2)~.

Output

Chứa một dòng ghi một số nguyên ~k~ mod ~10^6~.

Sample Input 1

3 3
###
#..
###
#..
###
###
#..
###
#..
#..

Sample Output 1

2

Sample Input 2

4 2
.#
##
.#
.#
.#
##
.#
##
#.
##

Sample Output 2

6138

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -4
    phidinh13  đã bình luận lúc 1, Tháng 7, 2021, 0:40

    Khó vl huhu ;.;