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 taskIn this problem, you have to find the sum of

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