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

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

Входные данные

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

Выходные данные

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

Пример

Існує в точності 5 способів викреслити слово logos: