Визначник

Дано матрицю (A) розміру (N $\times$ N). Кожен елемент цієї матриці може бути або (0), або (1). У кожному рядку всі одиниці розташовані підряд.

Вам потрібно обчислити значення визначника цієї матриці.

Вхідні дані

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

Вихідні дані

Виведіть одне число — значення визначника даної матриці.

Приклади