[USACO23DEC] Flight Routes G

Bessie 最近发现她最喜欢的摇滚艺术家 Elsie Swift 正在表演她最新的“时代之旅”音乐会！不幸的是，票卖光的太快了，所以 Bessie 考虑飞往另一个城市参加音乐会。“时代之旅”将在编号为 $1\dots N$ 的 $N$（$2 \le N \le 750$）座城市上演，每对满足 $i<j$ 的城市对 $(i,j)$ 都可能存在从 $i$ 到 $j$ 的一条**单向直飞航班**。 从城市 $a$ 到城市 $b$ 的一条**航线**是一个包含 $k\ge 2$ 座城市的序列 $a=c_1<c_2<\cdots<c_k=b$，使得对于所有的 $1\le i< k$，城市 $c_{i}$ 到城市 $c_{i+1}$ 有**单向直飞航班**。对于所有满足 $i<j$ 的城市对 $(i,j)$，你将被告知它们之间航线数目的奇偶性（$0$ 代表偶数，$1$ 代表奇数）。 在计划她的旅行行程时，Bessie 分心了。现在她想知道，有多少对城市间有**单向直飞航班**。可以证明答案是唯一的。

第一行包含整数 $N$。 接下来 $N-1$ 行，第 $i$ 行包含 $N-i$ 个整数。第 $i$ 行的第 $j$ 个整数表示从城市 $i$ 到城市 $i+j$ 的航线数目的奇偶性。

输出有单向直飞航班的城市对数。

3
11
1

2

5
1111
101
01
1

6

### 样例解释 1 有两条单向直飞航班：$1\rightarrow 2$ 和 $2\rightarrow 3$。有城市 $1,2$ 之间、$2,3$ 之间，仅包含一条单向直飞航班的航线各一条。还有城市 $1,3$ 之间的航线一条（$1\rightarrow 2\rightarrow 3$）。 ### 样例解释 2 有六条单向直飞航班：$1\rightarrow 2$，$1 \rightarrow 4$，$1\rightarrow 5$，$2\rightarrow 3$，$3\rightarrow 5$，$4\rightarrow 5$。这导致的航线数如下表所示： | 出发地\目的地 | 1 | 2 | 3 | 4 | 5 | | :-: | :-: | :-: | :-: | :-:|:-:| | 1 | 0 | 1 | 1 | 1 | 3 | | 2 | 0 | 0 | 1 | 0 | 1 | | 3 | 0 | 0 | 0 | 0 | 1 | | 4 | 0 | 0 | 0 | 0 | 1 | | 5 | 0 | 0 | 0 | 0 | 0 | 这与输入是相符的。 ### 测试点性质 - 测试点 $3-4$ 满足 $N \le 6$。 - 测试点 $5-12$ 满足 $N \le 100$。 - 测试点 $13-22$ 没有额外限制。