Имеются n пар натуральных чисел. Найдите количество вариантов, которыми можно выбрать в точности одно число из каждой пары так, чтобы сумма этих чисел была нечетной.

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

Первая строка содержит количество пар n. Каждая из следующих n строк содержит одну пару натуральных чисел.

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

Выведите искомое количество вариантов, которое не превосходит 1018.