Big Thanks to Clive Fraser for creating this problem!
Bob is a very superstitious person. He regards the number 7 as extremely lucky and tries to involve this number in everything that he does.
He intends to buy some gifts for his niece for her birthday. Bob buys gifts from the lucky gift shop. All of their gifts are marked with a luck
number. These luck numbers have integer values ranging from 0 to 9. Bob intends to buy up to 5 gifts for his niece and wants the total
luck value of these presents to be as lucky as possible. Since the total luck value of the presents could be a two-digit number, Bob decides
that the sum of the digits in the total luck value must come to 7. This can be achieved with a single-digit if the total luck value is 7.
Examples of lucky two-digit totals are 16 (1 + 6 = 7) and 25 (2 + 5 = 7).
The shop sells N different gifts. You will be given the luck number of each gift and must calculate the number of different combinations of
gifts which Bob can buy for his niece. Remember that the number of gifts bought must not be greater than 5. The number of combinations can be very large so you are asked to give the answer modulo 1000000007 (10^9 +7).
Since there is a great deal of data in this problem (the luck numbers of a large number of gifts) we will use a random number generator to create it, as follows. There will be N gifts in total. The Linear Congruential Generator has been used before in Code Abbey problems. A random value X(n) is generated using the formula:
X(n) = (A * X(n-1) + C) % M
In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the
modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random
value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data
for the problem. The formula above creates a reasonable sequence of roughly random values. However, these cannot be used directly for this
problem. For each random value X(n) we will create the required luck number R(n) using the formula:
R(n) = X(n) % 10
This expression creates a luck number in the range 0 to 9.
Consider a simple example with just 7 gifts in the shop (N = 7). This means that we need 7 random values to provide the luck data. If we
take the random seed X(0) to be 0 (it will not be 0 in the actual problem) then we can generate the 7 random numbers needed to create
this data. The first 7 values generated for X(n) are 700001 1819434 840897 1603084 1034921 1959835 404272. When we apply the formula for
R(n) we get the following luck numbers for the 7 gifts (we will label these gifts A, B, C, D, E, F and G).
A 1, B 4, C 7, D 4, E 1, F 5, G 2
There are 14 combinations of not more than 5 of these gifts where the total luck value is a number whose digits add to 7. These
combinations are listed below.
A B C D 1 + 4 + 7 + 4 = 16
A B D F G 1 + 4 + 4 + 5 + 2 = 16
A B G 1 + 4 + 2 = 7
A C E F G 1 + 7 + 1 + 5 + 2 = 16
A D G 1 + 4 + 2 = 7
A E F 1 + 1 + 5 = 7
B C D E 4 + 7 + 4 + 1 = 16
B C F 4 + 7 + 5 = 16
B D E F G 4 + 4 + 1 + 5 + 2 = 16
B E G 4 + 1 + 2 = 7
C 7 = 7
C D F 7 + 4 + 5 = 16
D E G 4 + 1 + 2 = 7
F G 5 + 2 = 7
Input/Output description: The first and only line of the input data will contain 2 space separated integers.
These are the random seed X(0) and the number of different gifts on sale in the shop. Your answer is the number of combinations of gifts
which Bob can buy (satisfying the conditions described above). Give your answer modulo 1000000007 (10^9 +7).
Example 1:
input:
0 7
answer:
14
Example 2:
input:
1085362 80
answer:
2855960
Example 3:
input:
891203 50000
answer:
971448562