Смерть – забавная штука. Обычно о ней рассуждают те, кто ещё ни разу не умирал. А вот те, кто уже помер, предпочитают помалкивать. Поэтому немногие знают, что на самом деле происходит с человеком после смерти. Бренное тело, разумеется, навсегда остаётся в толще земли... Но вот что происходит с человеческой душой, удалось доподлинно выяснить лишь Антону Хомякову – ученику легендарного Василия Тапкина (более подробно о г-не Тапкине рассказывается в задачах «Джедайский ребус» и «Джедайский ребус 2»).

Г-н Хомяков провёл ряд экспериментов и выяснил, что, как это ни печально, душа умершего не воспаряет к небесам. Впрочем, под землю она тоже не проваливается. Вместо этого она попадает на один из бесчисленных уровней Сумрака, где и обречена находиться до конца времён. Причём теоретически душу можно вернуть в Мир Живых и возродить в новом теле. Весь вопрос в том, каким именно образом это сделать...

Разумеется, Антон знал, что из Мира Живых можно напрямую попасть на любой уровень Сумрака. Нужно лишь знать Ключ – и Врата Миров распахнутся перед тобой. Ещё г-н Тапкин при жизни бывал на первых N уровнях, используя N Ключей K_i, найденных с помощью метода тыка. А вот подобрать ключ для (N+1)-го и последующих уровней Василию не удалось. Он лишь отметил, что для этого обязательно понадобятся N Чисел Сдвига C_i и Модулярное Число Y.

Но г-н Хомяков сумел превзойти своего Учителя и вывел универсальную формулу для расчёта Ключа K_i к Вратам любого уровня Сумрака. Вот эта формула: K_i = (K_i-1*C_N + K_i-2*C_N-1 + K_i-3*C_N-2 + ... + K_i-N*C₁) modulo Y.

Теперь Антон хочет организовать второе пришествие г-на Тапкина в наш грешный мир. Для этого ему осталось лишь вычислить Ключ к Вратам X-го уровня Сумрака, на котором томится в ожидании свободы душа Учителя.

Первая строка содержит целые числа N (1 ≤ N ≤ 100), X (N < X < 2²⁸) и Y (2 ≤ Y < 2²⁸). Вторая строка содержит N целых Ключей K_i (0 ≤ K_i ≤ 100). Третья строка содержит N целых Чисел Сдвига C_i (0 ≤ C_i ≤ 1).

Вывести искомый Ключ K_X.