Binary Transformation Count

Consider the following binary transformation on a fixed-length binary number. You are given four integers L, R, M and Y. Every integer x in the range [L, R] is written as an M-digit binary number (possibly with leading zeros). Then the following transformation is applied repeatedly until only one digit remains:

Step: Look at the two least‐significant bits of the current M-digit number. If both of these bits are 0, let X = 1; otherwise, let X = 0. Remove the two least‐significant bits and append the bit X at the end (i.e. in the least–significant position) of the remaining number. Repeat this operation until only one bit remains.

For example, consider the number 01001 (which is a 5–digit binary number):

1. 01001 → (lowest two bits: 0 and 1, not both 0, so X = 0) → 0100
2. 0100 → (lowest two bits: 0 and 0, both 0, so X = 1) → 011
3. 011 → (lowest two bits: 1 and 1, not both 0, so X = 0) → 00
4. 00 → (lowest two bits: 0 and 0, both 0, so X = 1) → 1

Thus, the final result of the transformation is 1.

Your task is to count how many numbers in the range [L, R] yield a final transformed value equal to Y (where Y is either 0 or 1).

---

Transformation Details

• Each number is represented in exactly M binary digits (with possible leading zeros).
• If M = 1 then the final value is the single bit itself.
• If M ≥ 2, let the binary representation be a₀ a₁ … a_M-1 (a₀ is the most–significant bit). Then the transformation can be described recursively as:

For M = 1: F(a₀) = a₀.
For M ≥ 2: F(a₀ a₁ … a_M-1) = { 0, if a₀ = 1; 1 - F(a₁ … a_M-1), if a₀ = 0. }

An equivalent interpretation is: for M ≥ 2, if the most–significant bit is 1 then the final answer is 0; if it is 0 then the final answer is the complement of the final value computed from the remaining M-1 bits. In particular, note that when all M bits are 0 the final answer alternates with M: it is 1 if M is even and 0 if M is odd.

---

Input Description

The input consists of a single line containing four integers separated by spaces:

• L: the lower bound of the range (0 ≤ L ≤ R < 2^M)
• R: the upper bound of the range
• M: the number of binary digits used to represent each number
• Y: the target final value (0 or 1)

Output Description

Output a single integer, the number of integers in the interval [L, R] whose final transformation result equals Y.

inputFormat

One line with four integers: L R M Y

outputFormat

A single integer representing the count of numbers in [L, R] with final transformation equal to Y.

sample

0 0 2 1

1