Given n pairs of positive integers. Count number of ways to choose exactly one number from each pair such that the sum of those numbers is odd.
First line contains number of pairs n. Each of the next n lines contains one pair of positive integers.
Print the required number of ways, which does not exceed 10^18
.