Cho xâu \(S\) có độ dài \(2 \times N-1\) và một lưới ô vuông \(A\) có kích thước \(N \times N\), mỗi ô trên lưới ghi một chữ cái. Một người tìm cách di chuyển bắt đầu từ ô ở góc trên trái đến ô ở góc dưới phải, mỗi lần di chuyển chỉ được quyền sang ô có chung cạnh ở bên phải hoặc phía dưới sao cho các chữ cái trong các ô trên đường di chuyển tạo thành xâu \(S\).

Yêu cầu: Cho trước lưới ô vuông \(A\) và xâu \(S\), hãy xác định số cách di chuyển thỏa mãn yêu cầu đặt ra.

Input

• Dòng đầu tiên ghi số \(N\) (\(2\le N \le 1000\));
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) chữ cái Latin in thường (thể hiện lưới chữ cái);
• Dòng cuối ghi xâu \(S\) gồm \(2 \times N-1\) chữ cái Latin in thường.

Output

• Một dòng ghi số nguyên là số cách di chuyển thỏa điều kiện Modulo cho \(10^6+3\).

Example

3
aaa
aba
baa
aabaa

5