Hi Codeforces,

I have been trying to solve this problem for quite a while but failed. Any help would be appreciated :)

The problem: Given an array of N integers and Q queries, in each query find number of subsets of size K of the subarray [L, R] such that each subsets' GCD is 1. Answer is modulo 10^9 + 7.
Problem Link

Constraints:
1 ≤ N ≤ 50000
1 ≤ L ≤ R ≤ N
1 ≤ Q ≤ 50000
1 ≤ A[i] ≤ 10000
1 ≤ K ≤ R − L + 1

I have tried with Mobius function and inclusion-exclusion technique but it takes too much time and memory (my code). I guess I will have to use some kind of data structure but can not figure out which one and how? Thank you.