ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1518. Jedi Riddle 3

Time limit: 1.5 second
Memory limit: 64 MB

Background

The death is a funny thing. It is discussed only by the ones, who never died, while those, who are already dead, prefer keeping silence. That is why few people know, what exactly happens with a human after his death. A body is undoubtedly remains under ground forever... But the way of a soul was discovered only by Anton Hamster, who was a disciple of legendary Vasily Slipman (you may look through the problems "Jedi riddle" and "Jedi riddle 2" for more information about Mr. Slipman).
Mr. Hamster carried out a sequence of experiments and found out, that, however it sounds pity, a soul neither soars into the sky nor falls under ground. It just finds oneself at one of the countless levels of the Twilight, where it is condemned to stay till the end of time. In theory, a soul may be returned into the Real World and resurrected in a new body. The only question is how to do it...

Problem

Surely, Anton knew, that it was possible to get to any level of the Twilight straight from the Real World. You should only know a Key - and the Gates of the Twilight will open before you. Inter vivos, Mr. Slipman himself visited N first levels using N Keys Ki he found by brute force. But Vasily failed to find the Key to the (N+1)-th and the following levels. He just made a remark, that one had to use N Shift Numbers Ci and the Modular Number Y.
But Mr. Hamster could excel his Teacher and succeeded in finding a universal formula for the Key Ki to the Gates of any level of the Twilight. Here is the formula: Ki = (Ki-1*CN + Ki-2*CN-1 + Ki-3*CN-2 + ... + Ki-N*C1) modulo Y.
And now Anton wants to organize the second coming of Mr. Slipman into our sinful world. The only thing he needs is to calculate the Key to the Gates of the Twilight's X-th level, where the Teacher's soul is concealed in expectation of freedom.

Input

The first line contains the integer numbers N (1 ≤ N ≤ 100), X (N < X < 228) and Y (2 ≤ Y < 228). The second line contains N integer Keys Ki (0 ≤ Ki ≤ 100). The third line contains N integer Shift Numbers Ci (0 ≤ Ci ≤ 1).

Output

You should output the desired Key KX.

Sample

inputoutput
3 6 73
12 91 65
1 1 0
22
Problem Author: Ilya Grebnov, Nikita Rybak, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge