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
"Looking for a Similar Assignment? Get Expert Help at an Amazing Discount!"
