You and two of your friends have just returned back home after visiting various countries.
Now you would like to evenly split all the souvenirs that all three of you bought.

Problem Description
Input Format.
The 1st line contains an integer n.
The 2nd line contains integers V1, ..., Vn separated by spaces.

Constraints.
1 ≤ n ≤ 20,
1 ≤ Vi ≤ 30 for all i.

Output Format.
Output 1, if it possible to partition V1,..., Vn into 3 subsets with equal sums, and 0 otherwise.

E.g. 1.
Input:
4
3 3 3 3
Output: 0

E.g. 2.
Input:
1
30
Output: 0

E.g. 3.
Input:
13
1 2 3 4 5 5 7 7 8 10 12 19 25
Output: 1
1 + 3 + 7 + 25 = 2 + 4 + 5 + 7 + 8 + 10 = 5 + 12 + 19.