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 `10`

.^{18}

Input example #1

3 1 2 3 5 4 1

Output example #1

4