Kevin has locked in and has begun grinding LeetCodes. He has been listening to too much Joe Rogan, and has figured out the optimal amount of caffeine required to achieve maximum productivity.

If Kevin goes under the amount of caffeine, he will not be perfectly productive. If he goes over, he will have a heart attack and die (we don't want that!). Therefore, it is very important that Kevin consumes exactly his optimal amount of caffeine.

To get the optimal amount of caffeine, Kevin must use multiple brands of energy drinks as they have varying amounts of caffeine. Since Shahid won big playing poker, he agrees to pay for however many energy drinks Kevin needs to achieve his caffeine requirements.

Kevin also wants to try multiple flavours of energy drink, so he wants to know how many ways he can drink his optimal amount of caffeine, given the caffeine content of each can of energy drink.

Input

The first line contains an integer ~n~ ~(1 \leq n \leq 50)~,the total number of energy drink flavours.

The second line contains ~n~ integers ~c_1, c_2, \dots, c_n~ ~(1 \leq c_i \leq 500)~, the amount of caffeine in each flavour.

The third line contains an integer ~t~ ~(1 \leq t \leq 5000)~, which is Kevin's optimal amount of caffeine.

Output

Return the number of combinations of caffeine concentrations that sum exactly to Kevin's optimal caffeine amount. If it is impossible to make the exact caffeine amount required, return $0$.

Example

Input 1

3
1 2 5
5

Output 1

4

There are four ways to drink ~5~mg using the concentrations given:

• ~5~
• ~2 + 2 + 1~
• ~2 + 1 + 1 + 1~
• ~1 + 1 + 1 + 1 + 1~

Input 2

1
2
3

Output 2

0

Kevin cannot drink ~3~ mg of caffeine using only ~2~ mg cans.

Input 3

1
10
10

Output 3

1