Определитель

Дана матрица A размера N×N. Каждый элемент матрицы равен 0 или 1. При этом в каждой строке все единичные элементы расположены подряд.

Требуется найти значение определителя этой матрицы.

Входные данные

В первой строке входного файла записано целое число N (1 ≤ N ≤ 10^6) — размер матрицы. В следующих N строках записаны по два числа l_i, r_i (1 ≤ l_i ≤ r_i ≤ N), означающие, что в i-ой строке в позициях с номерами l_i, ..., r_i стоят единицы, а остальные элементы равны нулю.

Выходные данные

В выходной файл выведите одно число — значение определителя данной матрицы.

Примеры