Arithmetic Progressions

Our thanks to Clive Fraser for creating this puzzle!

In this problem you will be given a sequence of N integers and are asked to find the number of subsequences, of length 3 or more, which are Arithmetic Progressions.

An Arithmetic Progression is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called the common difference of that arithmetic progression. For instance, the sequence 5, 7, 9, 11, 13, 15, … is an arithmetic progression with a common difference of 2. Similarly the sequence 19, 16, 13, 10, 7, … has a common difference of -3; and the sequence 9, 9, 9, 9, … has a common difference of 0.

If the initial term of an arithmetic progression is a(1) and the common difference of successive members is d, then the n-th term of the sequence is given by a(n) = a(1) + (n-1)d.

Because the number N of integers in the initial sequence is rather large, these values will be supplied using the Linear Congruential Generator. This 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 but these are too large for direct use in the problem. For each randomly generated number X(n) we will created the n-th term of the sequence S(n) = X(n) % 100. This ensures that the terms in the sequence lie in the range 0 to 99 inclusive.

Consider a small example, where N = 18. If we take the random seed X(0) to be 1234567 (it will not be 1234567 in the actual problem but will have some randomly chosen value) then we can generate the 18 random numbers needed to create the initial sequence. The 18 generated random numbers are 624038, 1570603, 1261059, 1927133, 532065, 488829, 123330, 1055457, 612510, 634981, 148731, 1873057, 1634273, 233843, 1998855, 990820, 1209411, 2012632. Using the calculation for S(n) above, we create the following sequence of 18 numbers.

38, 3, 59, 33, 65, 29, 30, 57, 10, 81, 31, 57, 73, 43, 55, 20, 11, 32

For this small example, we can easily pick out the subsequences of 3 or more elements which are arithmetic progressions. There are 13 in total. These are listed below. Note that the elements in a subsequence must be in the same order as the order in which they occur in the initial sequence.

3,  29, 55
3,  30, 57
3,  30, 57
29, 20, 11
29, 30, 31
29, 30, 31, 32
30, 31, 32
31, 43, 55
33, 57, 81
38, 29, 20
38, 29, 20, 11
59, 57, 55
59, 57, 55

These arithmetic progressions have lengths of just 3 and 4 but, as N gets larger, longer arithmetic progressions begin to appear. You will notice that the arithmetic progression 3, 30, 57 occurs twice. The first occurrence comes from the subsequence consisting of elements in positions 2, 8 and 15 of the initial sequence. The second occurrence comes from the subsequence consisting of elements in positions 2, 12 and 15 of the initial sequence. These are different subsequences so both are counted. A similar explanation covers the two occurrences of 59, 57, 55.

The actual problem will have N = 32000. The number of subsequences which are arithmetic progressions is now very large, so 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 problem size N. You need to determine the number of subsequences (of length 3 or more) which are arithmetic progressions. Give your answer modulo 1000000007.

Example 1:

input:
1234567 18

answer:
13

Example 2:

input:
809079 32000

answer:
970203516