Cho xâu ~S~ có độ dài ~2N-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.
• Dòng cuối ghi xâu ~S~ gồm ~2N-1~ chữ cái Latin in thường.

Output

• Một dòng ghi số nguyên là phần dư của phép chia số cách di chuyển thỏa điều kiện cho ~1000003~.

Sample Input 1

3
aaa
aba
baa
aabaa

Sample Output 1

5