JOI đang chơi một trò chơi với một bàn cờ dạng lưới gồm \(3\) hàng và \(N\) cột, cùng một số quân cờ. Trong trạng thái ban đầu, có ít nhất một ô đã được đặt quân và ít nhất một ô chưa được đặt quân.

Mục tiêu của trò chơi là lần lượt đặt thêm từng quân vào các ô chưa có quân, sao cho cuối cùng mọi ô trên bàn cờ đều có quân. Tuy nhiên, chỉ được đặt quân vào một ô khi ít nhất một trong hai điều kiện sau được thỏa mãn:

• Cả ô ngay phía trên và ô ngay phía dưới ô đó đều đã có quân.
• Cả ô ngay bên trái và ô ngay bên phải ô đó đều đã có quân.

JOI muốn biết có tất cả bao nhiêu thứ tự đặt quân để đi từ trạng thái ban đầu đến khi đạt được mục tiêu. Tuy nhiên, số lượng này có thể rất lớn.

Nhiệm vụ của bạn là thay JOI tính số lượng các thứ tự đặt quân từ trạng thái ban đầu đến khi đạt được mục tiêu, lấy dư cho \(1\,000\,000\,007\).

Yêu cầu

Cho trạng thái ban đầu của trò chơi, hãy viết chương trình tính số lượng các thứ tự đặt quân để đạt được mục tiêu, lấy dư cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), cho biết bàn cờ có \(3\) hàng và \(N\) cột.
• Mỗi trong \(3\) dòng tiếp theo chứa một chuỗi gồm \(N\) ký tự. Mỗi ký tự là o hoặc x. Ký tự thứ \(j\) từ trái sang (\(1 \le j \le N\)) của dòng thứ \(i\) trong ba dòng này (\(1 \le i \le 3\)) biểu diễn trạng thái ban đầu của ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang. Ký tự o cho biết ô đó đã có quân ở trạng thái ban đầu; ký tự x cho biết ô đó chưa có quân ở trạng thái ban đầu.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số lượng các thứ tự đặt quân để đạt được mục tiêu, lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

Tất cả dữ liệu vào thỏa mãn \(1 \le N \le 2\,000\).

Phân nhóm

1. 10 điểm: Ban đầu có không quá \(16\) ô chưa có quân; \(N \le 30\).
2. 12 điểm: Với mỗi ô chưa có quân ở trạng thái ban đầu, trong các ô kề ngay phía trên, phía dưới, bên trái và bên phải của nó, có không quá \(2\) ô chưa có quân.
3. 20 điểm: Ở trạng thái ban đầu, không có \(3\) ô chưa có quân liên tiếp theo chiều dọc; \(N \le 30\).
4. 38 điểm: \(N \le 300\).
5. 20 điểm: Không có ràng buộc bổ sung.

Ví dụ

3
oxo
xxo
oxo

14

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

149022720

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

0

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

228518545