Một băng giấy được chia thành \(3 \times n\) ô, mỗi ô được tô bằng màu đen hoặc màu trắng. Cần tìm cách tô để sau khi tô có thể cắt để nhận được một hình chữ nhật màu đen có diện tích bằng \(S\) từ các nhát theo đường chia ô của băng giấy.

Yêu cầu: Cho \(n\) và một số ô đã được tô, hãy đếm số cách tô vào các ô còn lại thỏa mãn yêu cầu trên.

Input

• Dòng đầu hai số nguyên \(n,s\).
• Ba dòng tiếp theo, mỗi dòng chứa một xâu (chỉ gồm ba ký tự W, B, #) độ dài \(n\) mô tả băng.

Output

• Gồm một dòng chứa một số là số cách tô thỏa mãn chia dư cho \(111539786\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 10^9, s \le 5\) và băng giấy ban đầu chưa tô bất kỳ ô nào (dữ liệu vào khi đó chỉ gồm hai số nguyên \(n,s\)).

Example

2 4
##
##
#W

2

2 4
##
#W
##

0