Please forget about such things.

There is nothing left that I want to say.

There are $n$ "fishies" in a shop arranged in a row, where the $i$-th fishy has a volume of $a_i$.

Yuki has a backpack with a volume of $V$. She plans to consider each fishy one by one from $1$ to $n$: if the volume of the current fishy is less than or equal to the remaining volume of the backpack, she puts the fishy into the backpack; otherwise, she does not. When a fishy of volume $x$ is put into the backpack, the remaining volume of the backpack decreases by $x$.

Since Yuki is a magical girl, she can set the initial volume $V$ of the backpack to any non-negative integer, but she cannot modify the volume of the backpack while considering the fishies.

Let $s_i$ denote the selection status of the $i$-th fishy; specifically, $s_i=1$ if the $i$-th fishy is put into the backpack, and $s_i=0$ otherwise. You need to find how many distinct sequences $s$ can be generated by the strategy described above.

Input

The first line contains an integer $c$, representing the subtask number to which this test case belongs. The sample cases satisfy $c=0$.

The second line contains an integer $n$.

The third line contains $n$ integers $a_1, \dots, a_n$.

Output

Output a single line containing a non-negative integer, representing the number of distinct sequences $s$ that can be generated.

Examples

Input 1

0
3
1 3 8

Output 1

4

Note

• When the initial backpack volume $V=0$, $s=\{0,0,0\}$;
• When the initial backpack volume $V=2$, $s=\{1,0,0\}$;
• When the initial backpack volume $V=5$, $s=\{1,1,0\}$;
• When the initial backpack volume $V=23$, $s=\{1,1,1\}$.

It is easy to prove that for any other non-negative integer $V$, the generated $s$ must be one of these $4$ types, so the answer is $4$.

Input 2

0
4
1 3 1 4

Output 2

6

Note

• When the initial backpack volume $V=0$, $s=\{0,0,0,0\}$;
• When the initial backpack volume $V=1$, $s=\{1,0,0,0\}$;
• When the initial backpack volume $V=3$, $s=\{1,0,1,0\}$;
• When the initial backpack volume $V=4$, $s=\{1,1,0,0\}$;
• When the initial backpack volume $V=7$, $s=\{1,1,1,0\}$;
• When the initial backpack volume $V=10$, $s=\{1,1,1,1\}$;

It is easy to prove that for any other non-negative integer $V$, the generated $s$ must be one of these $6$ types, so the answer is $6$.

Input 3

0
5
16 8 4 2 1

Output 3

32

Input 4

0
6
7 4 4 6 8 7

Output 4

9

Constraints

For all test cases:

• $1 \le n \le 2\cdot10^5$;
• For all $1 \le i \le n$, $1 \le a_i \le 10^9$.

This problem uses bundled testing.

• Subtask 1 (7 points): $n \le 18$.
• Subtask 2 (11 points): $n \le 100$; for all $1 \le i \le n$, $a_i \le 100$.
• Subtask 3 (8 points): $n \le 500$; for all $1 \le i \le n$, $a_i \le 500$.
• Subtask 4 (5 points): $n \le 500$.
• Subtask 5 (12 points): $n \le 8\cdot10^3$; for all $1 \le i \le n$, $a_i \le 8\cdot10^3$.
• Subtask 6 (15 points): $n \le 8\cdot10^3$.
• Subtask 7 (13 points): $n \le 8\cdot 10^4$.
• Subtask 8 (12 points): The sequence $a$ is guaranteed to be monotonically non-increasing.
• Subtask 9 (17 points): No special restrictions.