Arrays and gcd

Time limit0.5sMemory limit128 MB

Summary

Count arrays arr with elements in [1, num] whose running gcd array equals the given array C, modulo 1e9+7.

Level: Medium7 of 10
Topics: Number theory, Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

There are two integer arrays of size $N$ , called $arr$ and $C$ . They satisfy the following relation.

$C[0] = arr[0], \qquad C[i] = \gcd(C[i-1],\, arr[i]) \quad (1 \le i \le N-1)$

Here $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$ .

For example, $arr = [16, 16, 8, 16, 2]$ gives $C = [16, 16, 8, 8, 2]$ .

Given the array $C$ , find the number of arrays $arr$ that produce it, modulo $1000000007$ ( $10^9+7$ ). Every element of $arr$ is an integer between $1$ and $num$ .

Input

The first line contains two integers $N$ ( $1 \le N \le 10^5$ ) and $num$ ( $1 \le num \le 10^9$ ), separated by a space.

The second line contains the elements of the array $C$ , that is $C[0], C[1], \ldots, C[N-1]$ , separated by spaces. ( $1 \le C[i] \le num$ )

Output

Print the number of arrays $arr$ that satisfy the conditions, modulo $10^9+7$ , on the first line.

Examples4

Example 1
Input
```
3 900
900 450 225
```
Expected output
```
2
```
Example 2
Input
```
5 16
16 16 8 8 2
```
Expected output
```
8
```
Example 3
Input
```
4 10
6 4 2 2
```
Expected output
```
0
```
Example 4
Input
```
1 1000000000
7
```
Expected output
```
1
```