Gọi ~S_i~ là phần tử thứ ~i~ của tập ~S~, và ~K_x~ là số ước nguyên tố khác nhau của ~x~.

Vì ~1 \le S_i \le 10^6 \Rightarrow 1 \le K_{S_i} \le 7~.

Dễ thấy, số cặp số ~(x, y)~ (~x \le y~) nguyên tố cùng nhau và ~\text{lcm}(x, y) = S_i~ là ~2^{K_{S_i} - 1}~ (lưu ý: ta quy ước ~K_1 = 1~).

~\Rightarrow f(S) = \sum \limits_{i = 1}^{|S|} 2^{K_{S_i} - 1}~

Lúc này với mỗi truy vấn, ta sẽ đếm số tập hợp ~S~ khác nhau thỏa mãn:

• ~\sum \limits_{i = 1}^{|S|} 2^{K_{S_i} - 1} = n~

• ~l \le S_i \le r~

• Số phần tử của tập hợp ~S~ là nhỏ nhất.

Vì ta muốn số lượng phần tử thuộc tập ~S~ là nhỏ nhất, ta có thể áp dụng cách tham lam sau: lấy tối đa các số ~x~ trong đoạn có ~K_x = 7~, sau đó tiếp tục lấy tối đa các số có ~K_x = 6~, rồi đến ~K_x = 5~, ...

Giả sử, trong đoạn ~[l, r]~ có ~C_i~ số có ~K_x = i~ (có ~C_i~ số cố ~i~ ước nguyên tố khác nhau); và ta lấy được ~D_i~ số có ~K_x = i~. Đáp án cho truy vấn sẽ là ~\prod \limits_{i = 1}^{7} \binom{C_i}{D_i}~.

Để trả lời truy vấn, ta có thể tiền xử lý bằng prefix sum (tổng tiền tố) để nhanh chóng tìm được ~C_i~.

Độ phức tạp: ~O(n)~ tiền xử lý, ~O(1)~ trả lời truy vấn.

Code mẫu

#pragma GCC optimize("unroll-loops,02,no-stack-protector")
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1)
#define turnon(x,y) ((x)|(1<<y))
#define turnof(x,y) ((x)^(1<<y))
#define oo 1000000000000000000
#define pb push_back
#define all(x) x.begin(),x.end()
#define con(mask) mask=(mask-1)&mask
#define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())

const int mod=1e9+7;
using namespace std;

int q, n, l, r;

int cnt[1000017];
int dp[1000017][7];
int f[1000017], F[1000017];

int Pow(int p, int q) {
    if(q == 0) return 1;
    if(q == 1) return p % mod;

    int x = Pow(p, q / 2) % mod;
    x = x * x % mod;
    if(q % 2) x = x * p % mod;
    return x;
}
int nck(int n, int k) {
    if(k > n) return 0;
    return f[n] * F[n - k] % mod * F[k] % mod;
}
main()
{
    #ifndef ONLINE_JUDGE
    freopen("inp.inp","r",stdin);
    freopen("out.out","w",stdout);
    #endif //ONLINE_JUDGE

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    f[0] = F[0] = 1;

    for(int i = 1; i <= 1000000; i++) {
        f[i] = f[i - 1] * i % mod;
    }
    F[1000000] = Pow(f[1000000], mod - 2);

    for(int i = 999999; i >= 1; i--) {
        F[i] = F[i + 1] * (i + 1) % mod;
    }
    for(int i = 1; i * i <= 1000000; i++) {
        for(int j = i; j <= 1000000 / i; j++) {
            if(__gcd(i, j) == 1) cnt[i * j]++;
        }
    }

    for(int i = 1; i <= 1000000; i++) {
        int tmp = cnt[i];
        int d = 0;
        while(tmp % 2 == 0) {
            tmp /= 2;
            d++;
        }
        dp[i][d] = 1;

        for(int j = 0; j < 7; j++) {
            dp[i][j] += dp[i - 1][j];
        }
    }
    cin >> q;

    while(q--) {
        cin >> n >> l >> r;
        int res = 1;
        for(int i = 6; i >= 0; i--) {
            int tmp = dp[r][i] - dp[l - 1][i];

            int need = min(tmp, n / (1<<i));


            res = res * nck(tmp, need) % mod;
            n -= need * (1<<i);
        }
        if(n) cout << 0 << "\n";
        else cout << res << "\n";
    }
}
//      ProTeam
//(¯`·.·´¯) (¯`·.·´¯)
//`·.¸(¯`·.·´¯)¸ .·
//×°× ` ·.¸.·´ ×°×