Limits
1s, 512 MB

To become economically stable, Saturn has come up with a new kind of business, tree business.

At first, he will make two types of trees: type-1 trees and type-2 trees. In the ridiculous world Saturn lives, a tree can be made simply by combining some fruits where each distinct fruit is identified by a unique number. Saturn has an infinite amount of corrupted money, so he can buy any number of a specific fruit to make his trees. But there is a limit to how many fruits of a specific kind can be used to make a specific type of tree, if Saturn crosses that limit, the tree will turn ugly.

For example, let the maximum number of fruits with ID-1 in a type-1 tree be 4 and the maximum number of fruits with ID-2 in a type-1 tree be 3. The maximum limit of all other unmentioned fruits in a type-1 tree is 0. So how many kinds of distinct type-1 trees can Saturn make then? 20. Because two trees are different if they have a different number of a specific type of fruit. For example, a tree made by combining 3 fruits of ID-1 and 1 fruit of ID-2 is different from a tree made by combining 3 fruits of ID-1 and 2 fruits of ID-2. Note that Saturn can make a type-1 tree by 0 fruits of ID-1 or 0 fruits of ID-2 as well. Even more weirdly, a tree can be made even when number of all the fruits are 0! So, if there are 1 fruit of ID-1 and 2 fruits of ID-2 as limit for type-1 trees, there are 6 types of type-1 trees possible. They can be represented as 00, 01, 02, 10, 11, 12 where 11 means this tree has been made with 1 fruit of ID-1 and 1 fruit of ID-2.

Knowing the limits of fruits for both type-1 tree and type-2 tree, Saturn will first make all kinds of possible type-1 and type-2 trees in the first day. In this weird world, each type-1 tree becomes a new kind of type-2 tree in the next day, and each type-2 tree splits into a new kind of type-1 tree and a new kind of type-2 tree.

For example, if there are 5 type-1 trees and 4 type-2 trees in day 1, the 5 type-1 trees will become new 5 type-2 trees and 4 type-2 trees will split into 4 new type-1 trees and 4 new type-2 trees in day 2. So in day 2, there will be 4 type-1 trees and 9 type-2 trees.

Given **P**, **Q** and the initial maximum limits of fruits for type-1 trees and type-2 trees, you have to find the GCD (greatest common divisor) of the numbers of type-2 trees in day **P** and day **Q**. Since this number may be large, you have to print the answer modulo **M**.

The input starts with two integers **N1** and **N2**, how many kinds of fruits allowed for type-1 trees and type-2 trees respectively.

The following line contains **N1** space-separated integers, referring to the maximum limits of each of the distinct fruits for type-1 trees.

The next line contains **N2** space-separated integers, referring to the maximum limits of each of the distinct fruits for type-2 trees.

Finally, a line with 3 integers are given, **P**, **Q** and **M**, which are described in problem statement.

**Constraints:**

1 ≤ N1, N2 ≤ 104

1 ≤ maximum limit of any fruit ≤ 104

1 ≤ P, Q ≤ 1012

|P - Q| ≤ 2

1 ≤ M ≤ 109

Print the GCD of the numbers of type-2 trees in day **P** and day **Q**, modulo **M**.

Input | Output |
---|---|

2 3 1 2 1 1 1 1 2 3 | 2 |

The maximum limits of the fruits for type-1 trees are 1 and 2. So there can 6 kinds of type-1 trees possible (this example is also shown in problem description). Similarly, the number of distinct type-2 trees is 8. So in day 1, there will be 6 type-1 trees and 8 type-2 trees. In day 2, the 6 type-1 trees will become 6 type-2 trees and the 8 type-2 trees will split into 8 type-1 trees and 8 type-2 trees. So, in day 2, there will be 8 type-1 trees and 14 type-2 trees. Thus, the numbers of type-2 trees in day 1 and day 2 are 8 and 14. The GCD of these two numbers is 2 and 2 modulo 3 is also 2, so the answer is 2. |