The world-famous burglar Matvey received an order for an innovative safe produced by British Scientists, Inc. This safe is almost entirely made of adamantite, which does not lend itself to any of Matvey's drills. Therefore, its only weak point is a patented combination lock. Fortunately, Matvey stole the blueprints of the safe during its development, so he knows exactly how the lock works.
The code is entered using a keypad with numbers from zero to nine. As soon as the required number of digits is entered, the code is checked according to the following algorithm. The first entered digit is added to zero, then the second is subtracted, then this difference is multiplied by the third, and finally, the result is completely divided by the fourth. Then this algorithm is repeated for the next four digits, and so on until they run out. If the number of digits is not divisible by four, then the extra actions are simply discarded. If a division by zero is encountered during the execution of the algorithm, then it immediately crashes, blocking the safe. If the result is the number X - a secret constant that Matvey also knows - the lock opens.
Matvey carefully studied the keyboard and realized that he could determine from the fingerprints on the buttons which numbers are used in the code, and how many times. Then he became interested - how many combinations that fit this data open the lock? Combinations are considered different if they have a different order of numbers.
But alas, Matvey is not very good at mathematics, therefore, having easily completed the order, he asked this question to the world-famous hacker - you. Help Matvey.
Input
The first line contains two numbers N (1 <= n <= 8) and X (1 <= X <= 10^9) - the number of digits in the code and a secret constant. The second contains n digits separated by spaces. Of course, numbers can be repeated.
Output
It is necessary to output a single number - the answer to Matvey's question.
|
Enter |
Output |
|
40
2 2 3 6
|
4 |
2 1
1 1 |
0 |
(c) Daniil Kirionenko