You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有n种硬币，每种有2枚。求能组成的不同金额数目。

Input

第一行输入n，接下来一行输入n个正整数表示每种硬币的面值。（n不超过30，硬币面值不超过50）

Output

输出可能的金额数目。（没有选择硬币也算1种方案）

Samples

2
1 2

7

Limitation

1s, 1024KiB for each test case.