Langze Arrangement Query

This problem is inspired by a special data sequence and its description method. The original idea comes from a series of data where each level is constructed by describing the previous level. In the classical look-and-say sequence (often described in Wikipedia), one reads the previous level from left to right and groups consecutive identical numbers. For each group, the description is to state the number of appearances followed by the digit itself.

In this problem, we define a new structure called the Langze Arrangement. It is built as follows:

• Level 1 consists of a single integer Q (the initial data).
• For each level n (starting with n = 1), we construct level n+1 by describing level n in one of two ways:
  • If n is odd, use Rule A: read the level from left to right and for each maximal group of consecutive identical numbers, output two numbers — first the count of that number and then the number itself.
  • If n is even, use Rule B: read the level from left to right and for each maximal group of consecutive identical numbers, output two numbers — first the number itself and then its count.

For example, if Q = 1 then the sequence develops as follows:

1. Level 1 (given): [1]
2. Level 2 (describe Level 1 using Rule A, since 1 is odd): Group is [1] → one 1 → [1, 1].
3. Level 3 (describe Level 2 using Rule B, since 2 is even): Level 2 is [1, 1] (one group of 1's) → output: [1, 2] (number then count).
4. Level 4 (describe Level 3 using Rule A, since 3 is odd): Level 3 is [1, 2] → groups: [1] and [2] → output: [1, 1, 1, 2].
5. Level 5 (describe Level 4 using Rule B, since 4 is even): Level 4 is [1, 1, 1, 2] → groups: three 1's and one 2 → output: [1, 3, 2, 1].

The task is: given the initial number Q, a target integer x, and a layer index i (with Level 1 being the initial data), determine how many times x appears in the i-th layer of the Langze Arrangement.

Note: The description process alternates between two rules depending on whether the current level is odd (use Rule A) or even (use Rule B).

inputFormat

The input consists of three space‐separated integers:

• Q — the initial number (the only number in Level 1).
• x — the target number whose frequency is to be determined.
• i — the layer index (with Level 1 as the starting layer).

You may assume that the given values are such that the i-th layer can be generated using the described procedure.

outputFormat

Output a single integer representing the number of times x appears in the i-th layer of the Langze Arrangement.

sample

1 1 1

1