题目描述

$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$ 人を優勝者とする。

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

输入格式

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

$N$ $A_{2,1}$ $A_{3,1}$$A_{3,2}$ $:$ $A_{N,1}$$\ldots$$A_{N,N-1}$

输出格式

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

题目大意

竞赛图，把 $1,2,\dots,n$ 排成一列，每次把相邻两个留下胜者，问有多少人可能赢。

$n\leq 2000$

3
0
10

2

6
0
11
111
1111
11001

3

提示

制約

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

Sample Explanation 1

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