B. Bessie's Money
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer John is going to lunch with his six favorite cows: Alfred, Bessie, Codetigerorz, Dennis, Elsie, and Fran!

The meal cost $$$n$$$ dollars in total. FJ brought along several coins to pay. Specifically, for all $$$1 \le x \le 5$$$, he has $$$a_x$$$ coins which are worth $$$x$$$ dollars each.

The cows want to practice their English, so FJ needs to find a way to distribute coins to the cows in a way such that:

  • Each cow receives exactly one coin.
  • The sum of values of the coins the cows have is exactly $$$n$$$ dollars.

Note that FJ may have coins left over, or that it may be impossible to distribute coins in a way satisfying the conditions (for example, if FJ only has a single $$$1$$$-dollar coin, and the meal costs $$$5$$$ dollars).

Help FJ count the number of ways to distribute coins to the cows! Two ways are considered different if at least one of the cows is given a coin of a different value.

Input

The first line contains $$$n$$$, the total amount Farmer John needs to pay ($$$6 \le n \le 30$$$).

The second line contains $$$5$$$ integers describing how many coins of each type FJ has ($$$0 \le a_i \le 6$$$).

Output

Print the number of ways that the cows can pay $$$n$$$ dollars in total.

Example
Input
8
6 2 3 4 1
Output
21
Note

In the first test:

  • There are $$$6$$$ ways to give one of the cows a $$$3$$$-dollar coin and the rest $$$1$$$-dollar coins.
  • There are $$$15$$$ ways to give two of the cows a $$$2$$$-dollar coin and the rest $$$1$$$-dollar coins.

We can show that these are the only possible ways to make $$$8$$$ dollars with the given coins, so we output $$$6+15=21$$$.