z-jewelry
Mr Z loves gold jewelry. So he decided to open his own jewelry store in the center of the city. The price of a certain jewelry depends on it's mass N. For measuring the mass, he uses scales. He puts the jewelry on one side of the scales, and he has weights all with different masses that he puts on the other side of the scales. He noticed that for measuring a certain mass N, there is more than one combination of placing the weights in the scales. He asked you to count all the different ways to construct a given mass. Each weight can be used only once.
If the result overflows 1000000000, you need to return the result modulo 1000000000.
If the result overflows 1000000000, you need to return the result modulo 1000000000.
Input In the first line are two numbers N and M. N is the mass we want to achieve (1<=N<=1000000000), M is the number of weights (1<=M<=40). In the next M lines are given each of the masses of the weights. The masses of the weights will be between 1 and 1000000000 inclusive.
OutputYou should output the number of possibilities to construct the amount modulo 1000000000.
Input
Output
3 3
1
2
3Output
2Input
Output
5 9
1
2
3
4
5
6
7
8
9
Output
3Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.