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...

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 K_i 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 C_i and the Modular Number Y.

But Mr. Hamster could excel his Teacher and succeeded in finding a universal formula for the Key K_i to the Gates of any level of the Twilight. Here is the formula: 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.

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.

The first line contains the integer numbers N (1 ≤ N ≤ 100), X (N < X < 2²⁸) and Y (2 ≤ Y < 2²⁸). The second line contains N integer Keys K_i (0 ≤ K_i ≤ 100). The third line contains N integer Shift Numbers C_i (0 ≤ C_i ≤ 1).

You should output the desired Key K_X.