配点 : $1000$ 点

問題文

$N$ 人の参加するじゃんけん大会を行います。 参加者は人 $1$, 人 $2$, $\ldots$, 人 $N$ と呼ばれます。 どの $2$ 人についてもその $2$ 人がじゃんけんをしたときにどちらが勝利するかが事前に決まっています。 この情報は正の整数 $A_{i,j}$ ( $1 \leq j < i \leq N$ ) によって表され、

• $A_{i,j} = 0$ のとき、人 $i$ は人 $j$ に負けること
• $A_{i,j} = 1$ のとき、人 $i$ は人 $j$ に勝つこと

をそれぞれ表します。

大会は次のようにして行われます。

• $N$ 人の参加者を人 $1$, 人 $2$, $\ldots$, 人 $N$ の順に横一列に並べる。
• 列で連続している $2$ 人をランダムに選んで、その $2$ 人で試合を行い、負けた人を列から外す。 これを $N-1$ 回繰り返し、最後に残った $1$ 人を優勝者とする。

優勝する可能性のある人の人数を求めてください。

制約

• $1 \leq N \leq 2000$
• $A_{i,j}$ は $0$ または $1$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_{2,1}$

$A_{3,1}$$A_{3,2}$

$:$

$A_{N,1}$$\ldots$$A_{N,N-1}$

出力

優勝する可能性のある人の人数を出力せよ。

3
0
10

2

人 $1$ は人 $2$ に勝ち、人 $2$ は人 $3$ に勝ち、人 $3$ は人 $1$ に勝ちます。 最初に人 $1$ と人 $2$ が試合をすると人 $3$ が優勝し、 最初に人 $2$ と人 $3$ が試合をすると人 $1$ が優勝します。

6
0
11
111
1111
11001

3