Problem Description

A quantum laboratory recorded the states of $N$ qubits at times $1, 2, \dots, T$. Each state value is $0$ or $1$.

For any qubit and any time interval $[L, R]$ ($1 \leq L \leq R \leq T$), if the number of times the qubit’s state is $1$ within the interval is exactly $K$, then we say the qubit produces one valid superposition in this interval.

Now, please count: among all qubits and all time intervals, the total number of valid superpositions.

Input Format

The first line contains three integers $N, T, K$, representing the number of qubits, the number of time points, and the target count.

The next $N$ lines each contain $T$ integers ($0$ or $1$). The $i$-th line represents the state sequence of the $i$-th qubit over all time points.

Output Format

Output one line with one integer, indicating the total number of valid superpositions.

3 5 2
1 0 1 0 1
0 1 1 0 0
1 1 0 0 1

14

2 4 1
1 0 0 1
0 0 0 0

6

1 6 3
1 1 0 1 1 0

3

1 3 0
0 0 0

6

Hint

Sample Explanation 1

For the 1st qubit $1\ 0\ 1\ 0\ 1$, the intervals that satisfy the condition are: $[1,3]$, $[1,4]$, $[2,5]$, $[3,5]$. There are $4$ intervals in total.

For the 2nd qubit $0\ 1\ 1\ 0\ 0$, the intervals that satisfy the condition are: $[1,3]$, $[1,4]$, $[1,5]$, $[2,3]$, $[2,4]$, $[2,5]$. There are $6$ intervals in total.

For the 3rd qubit $1\ 1\ 0\ 0\ 1$, the intervals that satisfy the condition are: $[1,2]$, $[1,3]$, $[1,4]$, $[2,5]$. There are $4$ intervals in total.

Therefore, the total count is $4 + 6 + 4 = 14$.

Sample Explanation 2

For the 1st qubit $1\ 0\ 0\ 1$, the intervals that contain exactly $1$ state equal to $1$ are: $[1,1]$, $[1,2]$, $[1,3]$, $[2,4]$, $[3,4]$, $[4,4]$. There are $6$ intervals in total.

For the 2nd qubit $0\ 0\ 0\ 0$, there is no state equal to $1$ in any interval, so there are no intervals that contain exactly $1$ state equal to $1$.

So the answer is $6 + 0 = 6$.

Sample Explanation 3

The only qubit is $1\ 1\ 0\ 1\ 1\ 0$.

The intervals that contain exactly $3$ states equal to $1$ are: $[1,4]$, $[2,5]$, $[2,6]$. There are $3$ intervals in total.

Sample Explanation 4

The only qubit has state $0$ at all time points.

When $K = 0$, we need to count the cases where there are exactly $0$ states equal to $1$ in the interval, i.e., intervals where all values are $0$.

When $T = 3$, there are $\frac{3 \times 4}{2} = 6$ intervals in total, and all of them satisfy the condition, so the answer is $6$.

Constraints

For $30\%$ of the testdata, $N \leq 10$, $T \leq 100$.

For $60\%$ of the testdata, $N \leq 50$, $T \leq 500$.

For all testdata, $1 \leq N \leq 200$, $1 \leq T \leq 1000$, $0 \leq K \leq T$. It is guaranteed that all state values in the input are either $0$ or $1$.

Translated by ChatGPT 5