Coins 2

시간 제한2초메모리 제한512 MB

요약

1부터 n까지의 동전이 각각 주어진 개수만큼 있을 때, 일부를 사용해 거스름돈 없이 만들 수 있는 음이 아닌 정수 값의 가짓수를 센다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

In ICPCCamp, people usually use coins of values $1, 2, 3, \dots, n$ .

Bobo was very poor, he had only $a\_1, a\_2, a\_3, \dots, a\_n$ coins of values $1, 2, 3, \dots, n$ , respectively. He bought an item of an unknown value without making change.

The unknown item was of non-negative integer value. Find the number of possible values it may have had.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains one integer $n$ ( $1 \leq n \leq 15$ ).

The second line contains $n$ integers $a\_1, a\_2, \dots, a\_n$ ( $0 \leq a\_i \leq 10^9$ ).

It is guaranteed that the number of test cases does not exceed $100$ , and there is at most one test case where $n > 10$ .

출력

For each test case, output an integer which denotes the number of possibilities.

예제1

예제 1
입력
```
3
0 1 2
3
0 2 3
```
예상 출력
```
6
12
```