题目描述

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$。这导致的航线数如下表所示：

这与输入是相符的。

测试点性质

• 测试点 $3-4$ 满足 $N \le 6$。
• 测试点 $5-12$ 满足 $N \le 100$。
• 测试点 $13-22$ 没有额外限制。