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ụ:

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

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

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~.

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)~

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

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~

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