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.

Background

Special for beginners, ^_^

Description

小明有n本书，每本有不同页数。他选几本放入书包，总页数可能有多少种不同的情况？（n不超过30，每页书不超过40页）

Format

Input

第一行输入n，接下来一行输入n个正整数表示每本书的页数。

Output

输出可能的不同总页数数目。（什么都不装也视作1个方案）

Samples

3
2 3 5

7

Limitation

1s, 1024KiB for each test case.