### PROBLEM LINK:

**Author:** Sergey Nagin

**Tester:** Shiplu Hawlader

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM-HARD

### PRE-REQUISITES:

Solving Dynamic Programming with Matrix Expo

### PROBLEM:

In this problem Sereja is interested in number of arrays **A[1], A[2], …, A[N] (1 ≤ A[i] ≤ M, A[i] - integer)**

such that least common multiple (**LCM**) of all its elements is divisible by number **D**.

Please, find sum of answers to the problem with **D = L, D = L+1, …, D = R**. As answer could be large, please output it modulo (10^{9} + 7).

### TECHNIQUE:

I will suggest to specifically read the whole post given in pre-requisite if you are not aware about this technique.

Let there be **K** states, **s _{1},s_{2}…s_{K}**.

For each state

**s**where

_{i}**i = 1 to K**recurrence is defined as:

**f(n,s**.

_{i}) = sum {j=1 to K} c_{{i,j}}f(n-1,s_{j})We define a transition matrix

**M**where

**M[i][j]=c**.

_{{i,j}}Let’s consider

**M**. Sum of all elements in row

^{{N-1}}**i**will give us

**f(N,s**assuming

_{i})**f(0,i)=0**forall

**i**.

### EXPLANATION:

Let’s solve for a single **D** first. Let’s say **D** has prime factors **p _{1}^{a1}, p_{2}^{a2} … p_{K}^{aK}**, where all

**p**are unique.

_{i}We form a simple dp of

**dp[n,mask]**, which denotes the answer for

**N=n**and

**D**=product [p

_{i}

^{a_i}], if

**i**’th bit is set in

**mask**. So,

**mask**is a

**K**bit number.

A simple recurrence would be:

```
&ret = dp[n,mask]
primes[] //prime factors of D.
count[] //count[i] denotes count of i'th prime in D
ret=0
for i = 0 to size(primes)-1:
for j = 1 to M:
//if j is kept at n'th index
//and keeping it satisfies the i'th set bit condition
//ie. count of primes[i] in j is greater than or equal to count[i]
if count_prime(primes[i] in j) >= count[i]
//set the i'th bit, add to current ret
ret += dp[n-1, mask|(1<<i)]
```

So, we can clearly see that our **dp[n,x]** is dependent on **dp[n-1,y]**, where **x** and **y** are two different masks/states. We can use matrix exponentiation here because in one state in our dp, answer for **n** is dependent on answer for **n-1** and the transition among other states is not dependent on **n**.

So, we form the transition matrix, where we set at **transit[i][j]**, the number of ways to reach mask **j** from mask **i** . Sum of all elements in **(2 ^{K}-1)**'th (all bits of

**D**are set) row of

**N-1**’th power of this transition matrix, will give us the answer, in accordance with the technique explained above. Try to prove how this works.

So, complexity for single **D** is **O(log N * (2 ^{K*3}))**. Note matrix multiplication of sizes P*P takes O(P

^{3}).

And, maximum K is until 2

*3*5

*7*11*13… is smaller than 1000(since D<1000). So, max K is 4.

Total complexity for single

**D**is

**O(log N * 2**.

^{12})Doing it for 1000 such values of **D** will take **O(log N * 2 ^{22})** worst case. Note it will be really lower than that because of variation in

**K**.