Many thanks to Clive Fraser for creating this puzzle!
In this problem we will interpret sequences of digits as both strings and integers in different parts of the problem. Consider the list
[345, 93, 93, 76]. Next consider the items in the list as strings. We are allowed to remove any number of these, or none of them (but not all
of them) and then to join the remaining strings together, without changing the order, to form a single string. There are 4 items in the list
so there are 15 different ways of removing items from the list. Removing the 4th item gives 3459393. Removing the 1st and 3rd items
gives 9376. Removing the 1st, 2nd and 4th items gives 93. Removing no items gives 345939376. Note that removal of item 2 gives
3459376 and removal of item 3 gives 3459376. The resulting strings are the same but the removed items are from different positions. We
will regard such combinations as different for the purpose of the problem.
So far we have considered the digit sequences to be strings. Once we have performed the operation described above, we will consider the
resulting sequence to be a single integer. We want to know whether or not it is a multiple of 13. In the problem you will begin with a long
list of strings and must consider every combination that can be achieved by removing different combinations of strings, possibly removing no
strings but not removing all of them. For each combination, the resulting string is treated as an integer. You need to count the number of
these integers which are multiples of 13.
Since there will be a large number of strings in the problem, we will use a random number generator to create them, as follows. There will be
N strings 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. In the first stage of the problem we will
interpret these random values as strings rather than integers.
Consider a simple example with N = 5. This means that we need 5 random values to provide the initial list of strings. 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 5 random values needed to create this data.
The first 5 values generated for X(n) are 700001 1819434 840897 1603084 1034921. With 5 strings there are 31 allowed combinations,
resulting in 31 strings to consider as integers. You should be able to generate these integers and to verify that just 3 of them are
multiples of 13. These 3 are shown in the table below. Note that the combinations on the left are strings. These concatenate to give the
string in the centre. This is then interpreted as an integer and a check is made to see whether or not it is divisible by 13.
840897 . 1603084 = 8408971603084 = 13 x 646843969468
700001 . 1819434 . 1034921 = 70000118194341034921 = 13 x 5384624476487771917
1819434 . 1603084 . 1034921 = 181943416030841034921 = 13 x 13995647386987771917
Here dot symbol (.) represents concatenating arguments as strings.
We are interested only in the number of multiples of 13. The calculations presented above are given only in order to clarify the problem.
You will be given a seed for the random number generator and the number N of strings required in the original list. The number of string
combinations created using the approach described above is clearly very much greater than N. The number of multiples of 13 is likely to be
very large. For this reason you are asked to give the answer modulo 1000000007 (10^9 +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 N of strings in the initial list. Your answer is a single integer, the number of multiples of 13 (modulo 1000000007)
when the final strings are considered as integers.
Example 1:
input:
0 5
answer:
3
Example 2:
input:
238019 20
answer:
80503
Example 3:
input:
0 400000
answer:
446795769