E. Interval (1000 points)

Bertie recently bought a multimedia smartphone with a touch screen, to edit his drum recordings while on the road. He bought an expensive mixer program that was obviously optimized for much larger screens, resulting in all the little knobs and switches being too small. Whenever he tries to operate the GUI with his finger, he toggles a group of switches instead of a single switch. The more switches are turned on, the higher the power consumption of the expensive amplifiers is.

In this task, you will need to simulate Bertie's actions and estimate total power consumption by summing how many of the important switches were on during the simulation.

Given n switches numbered from 0..n-1. Each switch is either turned on or off. Initially all of them are off.


There are two operations Bertie can perform on the switches and each of them has two parameters, a and b:
operation description
toggle(a,b) toggle all switches in the closed interval [a,b]
query(a,b) query how many switches are turned on in the closed interval [a,b] (these are the important switches)

Your task is to simulate a sequence of k operations and calculate the sum of all query results.


The simulation details are specified below using pseudo code.

function seed(s) {
	x := s

function rand() {
	x := (6364136223846793005*x + 1442695040888963407) mod 2^64
	return x div 2^32

function simulation(n, k, p, s) {
	sum := 0
	repeat k times
		len := rand() mod n
		a := rand() mod (n-len)
		b := a+len
		r := rand()
		if r < p then
			sum := sum + query(a, b)
			toggle(a, b)
		end if
	end repeat


only one line: n k p s


only one number: the sum of all of the answers for the queries

Example input

10 10 2147483648 12345678987654321

Example output


Note: in this example the steps were

toggle(1, 6)
toggle(2, 7)
toggle(6, 6)
toggle(1, 2)
query(0, 6)
toggle(0, 8)
query(1, 7)
query(1, 3)
query(6, 7)
toggle(1, 8)