e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic Programming - Linear

Odd sum

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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
1 2
3 5
4 1
Output example #1
4