Sum of Keys in the Leaves

     

Image 1. Example of a binary tree which corresponds to Example 1 bellow. The sum of keys in the leaves is equal to 81.

The task

In this problem, you have to find the sum of all keys in the leaves of a given binary tree.

---

Input

The input contains a single text line with eight positive integers A, B, M, L1, L2, L3, D, R separated by one or more spaces. These parameters regulate the shape of the tree and specify the node keys as follows:
Suppose a node X contains key with value K. Then

• X has no children if K < L1 or if the depth of X is D,
• X has only left child if L1 ≤ K < L2,
• X has only right child if L2 ≤ K < L3,
• X has both children if L3 ≤ K.
• If left child of X exists then its key value is equal to (A×K + B) mod M.
• If right child of X exists then its key value is equal to (A×K + 2×B) mod M.

Input value R is the value of the key in the root of the tree. It holds, L1 < L2 < L3. All input values are less than 10000. The number of nodes in the tree does not exceed 1.1×10⁶. We remind you that the depth of the root is 0.

Output

The output contains a single text line with one integer equal to the sum of all keys in the leaves of the input tree.

Example 1

Input

31 17 43   5 15 23   5   30

Output

81

The input tree of Example 1 is depicted in Image 1 above.

Example 2

Input

117 241 2039   250 300 450   5    555

Output

11251

Example 3

Input

285 242 2053   260 310 450   10   682

Output

207229

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set