Background

Special for beginners, ^_^

Description

给出n件物品,每件物品有一个体积 V,求从中取出若干件物品能够组成的不同的体积和有多少种可能。例如，n=3,V=(1,3,4),那么输出 6,6 种不同体积和具体为 1、3、4、5、7、8。

Format

Input

第 1行1 个正整数,表示no
第 2行n个正整数,表示 V,每两个数之间用一个空格隔开。

Output

一行一个数,表示不同的体积和有多少种可能。

Sample 1

Input

3
1 3 4

Output

6

Limitation

1s,64MB for each test case.
对于30%的数据满足n≤5，vi≤10;
对于60%的数据满足n≤10，vi≤20;
对于100%的数据满足n≤20，1≤vi≤50;

Source

Vijos Original