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.
Input
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
Output
Print the GCD of the numbers of type-2 trees in day P and day Q, modulo M.
Sample
| 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. | |
