eolymp
Problems

Лінія

Лінія

Орися розставила на аркуші в клітинку N2 літер у формі квадрата N*N і хоче викреслити однією лінією деякі літери у такий спосіб: вона починає викреслювати літери, починаючи з лівої верхньої букви, і веде лінію то праворуч, то вниз; останньою літерою вона викреслює праву нижню. Таким чином, дівчина викреслить рівно 2N-1 літеру. При цьому Орися хоче, щоб уздовж лінії, яку вона проведе, було записано певне чарівне слово.

Завдання

Напишіть програму, яка для заданих розташування літер і чарівного слова визначить, у скільки різних способів Орися може його викреслити, та виведе відповідь за модулем простого числа 1 000 003.

Вхідні дані

У першому рядку вхідного файла записано натуральне число N (2 ≤ N ≤ 1000) — довжину сторони квадрата з літер. У наступних N рядках записано по N малих літер латинської абетки (не обов’язково різних), що задають розташування літер. Пробілів між літерами немає. Далі записано чарівне слово, що складається з 2N-1 літери (усі — малі літери латинської абетки, не обов’язково різні).

Вихідні дані

Вихідний файл повинен містити єдине число — остачу від ділення кількості способів, у які Орися може викреслити чарівне слово, на число 1 000 003.

Оцінювання

Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:

1. 25 % балів: 2 ≤ N ≤ 10.

2. 30 % балів: 10 < N ≤ 100.

3. 45 % балів: 100 < N ≤ 1000.

Пояснення. Є рівно 5 способів викреслити слово logos:

prb7384_

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
3
loc
ogo
gos
logos
Output example #1
5
Author Данило Мисак
Source XXVIII Всеукраїнська олімпіада з інформатики 2015 р.