ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1518. Джедайский ребус 3

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ

Вступление

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

Задача

Разумеется, Антон знал, что из Мира Живых можно напрямую попасть на любой уровень Сумрака. Нужно лишь знать Ключ – и Врата Миров распахнутся перед тобой. Ещё г-н Тапкин при жизни бывал на первых N уровнях, используя N Ключей Ki, найденных с помощью метода тыка. А вот подобрать ключ для (N+1)-го и последующих уровней Василию не удалось. Он лишь отметил, что для этого обязательно понадобятся N Чисел Сдвига Ci и Модулярное Число Y.
Но г-н Хомяков сумел превзойти своего Учителя и вывел универсальную формулу для расчёта Ключа Ki к Вратам любого уровня Сумрака. Вот эта формула: Ki = (Ki-1*CN + Ki-2*CN-1 + Ki-3*CN-2 + ... + Ki-N*C1) modulo Y.
Теперь Антон хочет организовать второе пришествие г-на Тапкина в наш грешный мир. Для этого ему осталось лишь вычислить Ключ к Вратам X-го уровня Сумрака, на котором томится в ожидании свободы душа Учителя.

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
3 6 73
12 91 65
1 1 0
22
Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge