As you know, chipmunks live a years. The chipmunks are loving beings, so every year new ones are born among them. Namely, if in a year y in some place there were only b chipmunks, then in the year y + 1 will be born b more.

Recently, Vasya has robbed the shop. Since Vasya knows chipmunks very well, he can determine their age. It was this that the robber took up on the very first day of his acquaintance with his prey. To his surprise, among the animals there was exactly n1 chipmunks of 1 year age, exactly n2 chipmunks of age 2 and so on.

Now Vasya wants to know how many chipmunks he will have in k years. And since he has a great dislike for large numbers since his school years, he wants to see this number modulo m.

Input

First line contains number a (1 ≤ a ≤ 5) - lifetime of the chipmunks. Next line contains numbers n1, n2, ..., na (0 ≤ ni ≤ 100) - the number of chipmunks at age 1, 2, ..., a years correspondingly. The last line contains two numbers k and m (0 ≤ k ≤ 109, 1 < m ≤ 109) - the time interval of interest, and the modulo by which you want to print the number of chipmunks.

Output

Print the number of chipmunks in k years by modulo m.