Circular Light Switchers

There are n lamps arranged in a circle and numbered 1 through n clockwise. At time 0, each lamp i has an initial state a_i (0 means off and 1 means on). At each subsequent time step, the state of every lamp is updated according to the following rule:

The new state of lamp i will be 0 (off) if the current state of lamp i and the current state of its clockwise neighbor (lamp i+1; lamp 1 is the neighbor of lamp n) are the same; otherwise, it will be 1 (on).

Formally, if we denote by a_i(t) the state of lamp i at time t (with indices taken modulo n), then for t ≥ 0:

$$ a_i(t+1) = a_i(t) \oplus a_{i+1}(t), \quad 1 \le i \le n, $$

where \(\oplus\) denotes the XOR operation (i.e. addition modulo 2).

You are given three numbers: n (the number of lamps), t (the number of time steps), and k (the lamp index to query). Also, the initial configuration a1, a2, \dots, an is provided. Your task is to determine the state (0 or 1) of the k-th lamp at time t.

Hint: Because the update rule is linear over \(\mathbb{F}_2\), you can view the transformation as a convolution. In fact, if you define a polynomial A(x) such that A(x)=a₀+a₁x+\cdots+a_n-1x^n-1 (with indices adjusted to 0-indexing), then the update rule can be written (after a re-indexing) as multiplying by \(1+x^{-1}\) modulo \(x^n-1\) (since lamp i gets updated with the XOR of its current state and that of lamp i+1). Thus the state after t steps is given by:

$$ A^{(t)}(x)= (1+x^{-1})^t \cdot A(x) \,\,\mod (x^n-1), $$

and the k-th lamp's state (with k converted to 0-index) is the coefficient corresponding to \(x^{k-1}\) in \(A^{(t)}(x)\).

inputFormat

The input consists of two lines. The first line contains three integers n, t, and k (1 ≤ k ≤ n): the number of lamps, the number of time steps, and the 1-indexed lamp to query, respectively. The second line contains n space-separated integers, each being 0 or 1, representing the initial state of the lamps in order.

outputFormat

Output a single integer, the state (0 or 1) of the k-th lamp at time t.

sample

3 1 1
0 1 0

1