Bài toán được diễn giải lại như sau:

Bài toán: Chia bánh quy

Peter đến thăm nhà của hai chị em Anna và Maria và phát hiện rằng họ có rất nhiều bánh quy được phân bố vào các túi để lưu trữ. Vì có quá nhiều bánh quy, Peter quyết định rằng sẽ chẳng có gì to tát nếu anh ấy lấy trộm một vài túi bánh. Tuy nhiên, anh ấy muốn đảm bảo rằng Anna và Maria sẽ không cãi nhau vì những chiếc bánh này.

Để tránh xảy ra tranh chấp, Peter chỉ muốn lấy đi một số túi bánh quy sao cho tổng số bánh quy còn lại trong các túi có thể chia đều thành hai phần (số bánh còn lại là một số chẵn). Hãy tính xem có bao nhiêu cách chọn túi để đảm bảo điều kiện này.

Dữ liệu vào:

1. Dòng đầu tiên chứa số nguyên N ~(1 \leq N \leq 10^6)~ — số lượng túi bánh quy mà Anna và Maria có.
2. Dòng thứ hai chứa N số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \leq A_i \leq 10^6)~ — số lượng bánh quy trong từng túi.

Dữ liệu ra:

• Một số nguyên ~K~ — là số cách chọn túi bánh sao cho tổng số bánh còn lại trong các túi là một số chẵn. Nếu không có cách nào thì in ra ~0~.

Ví dụ:

Input

1
1

Output

1

Input

2
1 1

Output

0

Input

10
1 2 2 3 4 4 4 2 2 2

Output

8

Giới hạn:

• ~40\%~ số test với ~1 \leq N \leq 1000~.
• ~60\%~ số test với ~1 \leq N \leq 10^6~.