no of ways of having an A array of length N formed using only [1,2,…M] 1<=M<=10 with condition that gcd(A[i],A[i+1]) 1

Input N M

Constraints 1<=N<=1e10 1<=M<=10

Test Case1: 1 1

Output: 1

Explanation: { [1] }

Test Case2: 2 2

Output : 3

Explanation: { [1, 1] , [1, 2] , [2 , 1]}

I am not able to understand the question.

more formally the question is asking for number of arrays of length n with consecutive digits as coprime using elements of array belonging to range [1,M] given n amd m find ans%k;

k=1e9+7;

Thanks for explaining the problem.

Maybe we can try this approach.

`DP[i][j]`

= # number of ways such that the length of array is `i`

now and the element at position `i`

is `j`

.

We can fill this DP array such that going form `i`

to `i+1`

we need to find for each chosen `j`

the number of coprimes to it and add those.

That is

DP[i][j] = \sum_{k=1}^{m} DP[i-1][k] such that gcd(j,k) = 1

Final answer \sum_{k=1}^{m} DP[n-1][k]

Don’t forget the modulo.

N is huge(N = 1e10)?

I think there is something combinotorics with dp.

As m is small (10) we can think like filling the subsets in the array.May be…

I did not notice the constraints.

I think we can use fast matrix exponentiation to do this in log(n) .

The matrix is m * m and matrix[i][j] = 1 if gcd(i,j) = 1 else 0.