H. Candyholic
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

As everyone knows, Michael loves food. With Halloween around the corner, he also has bucketfuls of candy that he has been meaning to get rid of. He decided to split up his candy into $$$n$$$ goody-bags and hand them out to some of his friends. He has a total of $$$k$$$ friends, and wants to ensure the following:

  • Each friend should receive at least one bag of candy.
  • Michael doesn't want to mix around the bags, so each friend should receive a contiguous subarray of the bags (refer to the sample for further clarification).
  • These subarrays should also always be ordered, so the first friend will receive the first subarray in the partition, the second friend gets the next subarray, and so on.
  • Michael is a math fanatic and simultaneously wants to mess with his friends. Thus, each subarray should either have size $$$1$$$, or have the $$$\gcd$$$ of its elements be $$$1$$$.

As a reminder, $$$\gcd(a,b)$$$ is the greatest positive integer that is a factor of $$$a$$$ and $$$b$$$. The $$$\gcd$$$ of an array $$$A$$$ is the greatest positive integer that is a factor of all numbers in the array $$$A$$$, or:

$$$$$$\gcd(A_1, A_2, \ldots, A_N) = \gcd(\gcd(\ldots(\gcd(A_1, A_2), A_3)\ldots), A_N)$$$$$$

Help Michael find the total number of partitions he can create!

Input

The first line of input contains two integers $$$n$$$ ($$$5 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$2 \le k \le \min(200, n)$$$), the number of goody-bags and the number of friends Michael is giving candy to.

The second line contains $$$n$$$ integers, where $$$a_n$$$ ($$$1 \le a_n \le 10^9$$$) denotes the number of candies in the $$$n$$$th bag.

Output

Output a single integer, denoting the number of possible partitions. This number may be very large, but Michael wants to add a further spook by avoiding the common modulos. Thus, output your answer under modulo $$$10^9 + 3773 \cdot 263$$$.

In case you're curious, this modulo is also a safe prime, just like $$$10^9 + 7$$$!

Example
Input
5 2
2 7 3 6 4
Output
3
Note

In the sample, we have the following partitions:

  • $$$[2]$$$ and $$$[7,3,6,4]$$$: This works
  • $$$[2,7]$$$ and $$$[3,6,4]$$$: This works
  • $$$[2,7,3]$$$ and $$$[6,4]$$$: This fails (the latter $$$\gcd$$$ is $$$2$$$)
  • $$$[2,7,3,6]$$$ and $$$[4]$$$: This works