Flight Routes

문제

Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in $NN$ ($2\le N\le 7502\backslash le\; N\backslash le\; 750$) cities labeled $1\dots N1\backslash dots\; N$, and for each pair of cities $(i,j)(i,j)$ with there either exists a single direct flight from $ii$ to $jj$ or not.

A flight route from city $aa$ to city $bb$ () is a sequence of $k\ge 2k\backslash ge\; 2$ cities such that for each , there is a direct flight from city $c_{i}c\_i$ to city $c_{i+1}c\_\{i+1\}$. For every pair of cities $(i,j)(i,j)$ with , you are given the parity of the number of flight routes between them (0 for even, 1 for odd).

While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

입력

The first line contains $NN$.

Then follow $N-1N-1$ lines. The $ii$th line contains $N-iN-i$ integers. The $jj$th integer of the $ii$th line is equal to the parity of the number of flight routes from $ii$ to $i+ji+j$.

출력

Output the number of pairs of cities with direct flights between them.