Беси недавно узнала, что её любимая исполнительница Эльза Свифт отправилась
в концертный тур. Однако билеты продали так быстро, что Беси планирует полететь
в другой город, чтобы посетить концерт. Тур пройдёт в \(N\) (\(2\le N\le 750\)) городах,
помеченных \(1\dots N\), и для каждой пары городов \((i,j)\) где \(i<j\) или существует
прямой перелёт из \(i\) в \(j\) или нет.
Полётный маршрут из города \(a\) в город \(b\) (\(a<b\)) это последовательность
из \(k\ge 2\) городов \(a=c_1<c_2<\dots<c_k=b\) таких, что для каждого
\(1\le i<k\), существует прямой перелёт из города \(c_i\) в город \(c_{i+1}\).
Для каждой пары городов \((i,j)\) где \(i<j\), Вам задана четность количества
полетных маршрутов между ними (0 для чётных, 1 для нечётных).
Беси хочет узнать, сколько пар городов имеет прямые перелёты между ними.
Можно доказать, что ответ определяется уникально.
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит
\(N\).
Затем следуют \(N-1\) строк. \(i\)-ая строк содержит \(N-i\) целых чисел.
\(j\)-ое целое число в этой строке равно четности количества полётных маршрутов
из города \(i\) в город \(i+j\).
ФОРМАТ ВЫВОДА (на экран):
Выведите количество пар городов с прямыми полётами между ними.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
11
1
|
2
|