Đồ chơi XYZ

View as PDF

Submit solution

Points: 0.86 (partial)
Time limit: 0.25s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Online Informatics Olympiad '09Day 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.



  • -2
    phidinh13   commented on July 1, 2021, 7:40 a.m.

    Khó vl huhu ;.;