Counting Direct Flights

Bessie recently discovered that her favorite rock artist, Elsie Swift, is performing her new "Time Travel" concert tour! Unfortunately, the tickets sold out too fast, so Bessie is considering flying to another city to attend the concert. The tour will take place in N cities numbered from 1 to N (2 ≤ N ≤ 750). For every pair of cities (i, j) with i < j, there might be a one-way direct flight from city i to city j.

A flight route from city a to city b is defined as a sequence of k ≥ 2 cities, a = c₁ < c₂ < … < c_k = b, such that for every 1 ≤ i < k, there exists a direct one‐way flight from city c_i to city c_i+1. For each pair of cities (i, j) with i < j, you are given the parity of the number of flight routes between i and j (0 for even, 1 for odd). It is guaranteed that these parities uniquely determine the number of direct flights.

Your task is to compute the number of pairs of cities that have a one‐way direct flight. All calculations regarding the number of flight routes should be interpreted in modulo 2 arithmetic, i.e., using the field \(\mathbb{F}_2\). In particular, note that in \(\mathbb{F}_2\), addition is equivalent to the XOR operation and multiplication is equivalent to the AND operation.

The relation between the direct flights and the given parity is as follows. Let \(x_{ij}\) (with 1 ≤ i < j ≤ N) be a binary variable indicating whether there is a direct flight from city i to city j (1 if present, 0 otherwise), and let \(f_{ij}\) be the parity (0 or 1) of the total number of flight routes from i to j. Then for every pair (i, j) with i < j, we have: \[ f_{ij} = x_{ij} + \sum_{k=i+1}^{j-1} \Bigl( x_{ik} \cdot f_{kj} \Bigr) \pmod{2}. \] Using this recurrence relation, one can uniquely determine \(x_{ij}\) for all valid pairs. Your final answer is the sum of \(x_{ij}\) over all pairs (i, j) with i < j.

inputFormat

The first line contains a single integer N (2 ≤ N ≤ 750) indicating the number of cities.

Then N-1 lines follow. The i-th of these lines (1-indexed) contains N-i integers. The j-th integer on the i-th line (corresponding to cities i and i+j) is 0 or 1, representing the parity \(f_{i,i+j}\) (0 for even, 1 for odd) of the number of flight routes from city i to city i+j.

outputFormat

Output a single integer—the number of pairs of cities (i, j) with i < j that have a direct flight from i to j.

sample

2
1

1