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.

Input

First line contains number of pairs n. Each of the next n lines contains one pair of positive integers.

Output

Print the required number of ways, which does not exceed 1018.