## 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.

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