Problem Statement

Let p[0], p[1], ..., p[N-1] be a permutation of integers between 0 and N-1, inclusive. A binary search tree is a rooted binary tree with an integer value stored at each node. We use the following pseudocode to construct a binary search tree from the permutation p:

Create the root and put p[0] there
For each i in (1, 2, ..., N-1)
	Call insert(root, p[i])

Procedure insert(vertex V, integer X)
	If X < number at V
		If V has left child
			Call insert(left child of V, X)
		Else
			Create new left child of V with value X
	Else
		If V has right child
			Call insert(right child of V, X)
		Else
			Create new right child of V with value X
	End
End

You are given three ints: N, seed and limit. Use the following pseudocode to generate the permutation p (be sure to use 64-bit integers in computations where needed; note that '/' represents integer division and % represents remainder):

X := seed
For each i in (0, 1, ..., N-1)
	p[i] := i
	X := (X * 295397169) % 1073741789;
	If (X * 1000000) / 1073741789 < limit
		X := (X * 295397169) % 1073741789
		// generate j within [0, i]
		j := (X * (i + 1)) / 1073741789
		// j <= i, so p[j] is already initialized
		swap(p[i], p[j])
	End
End

John constructed a binary search tree from the generated permutation using the pseudocode described above. Return the sum of the heights of all nodes in the constructed tree. The height of a node V is the number of nodes in the path from the root to V.

Definition

Notes

Constraints

Examples