Ordered trees

Quido is becoming familiar with binary trees. He noticed that when a numerical key is assigned to each node various new properties of the tree may arise. For example, the values on each path from the root to a leaf might be sorted in non-desreasing order in a similar way as it is typical for binary heaps. Quido chose to call such trees ordered trees. Many trees are not ordered and to measure their un-orderliness Quido introduced a notion of displacement index. The displacement index of a node n is the number of all descendants of n which key value is smaller than the key value of n. The displacement index of the tree is the sum of displacement indices of all its nodes. Obviously, a tree is an ordered one exactly when its displacement index is equal to zero. The image bellow depicts an example of binary tree which displacement index is 17.
A node b is a descendant of a node a if the path from b to the root of the tree contains a.

     


Image 1. Example of a binary tree which displacement index is 9. Non-zero displacement indices are written at the respective nodes. Each green arrows represents a pair of nodes in which the descendant has a smaller key value.

The task

Compute the displacement index of a given binary tree.

Input

To avoid voluminous input data the following simplifying concept is used. Let X, A, M, D be positive integers. For the input tree T it hods:
1. X is the key value of the root of T.
2. The depth of T is less or equal to D.
3. When the key value of a node is greater or equal to A than the node is a leaf.
4. When the depth of a node is less than D and its key value k is less than A then there are two children of this node in T. The key value of the left child is 2 + (k2 mod M) and the key value of the right child is 3 + (k2 mod M).

The input contains one text line with the values X, A, M, D in this order separated by space. The value of D is less than 25, the other input values do not exceed 109.

Output

The otuput contains one text line with integer equal to the displacement index of the input binary tree.
The output value does not exceed 109.

Example 1

Input
2 52 99 4
Output
9
The input tree is depicted in the Image 1.

Example 2

Input
13 18 21 8
Output
4

Example 3

Input
55 133 143 20
Output
8748936

Example 4

Input
3 1282500 1299689 24
Output
252222855

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