Light OJ 1298 / DP - Number Theory

/***
 created: 2023-03-05-16.51.54
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define all(we) we.begin(),we.end()
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define nl '\n'

const ll mod=1e9+7;
#define maX 100008
bool marked[maX+2];
vector<ll>p;
void sieve()
{
    marked[0]=1;
    marked[1]=1;
    for(ll i=4; i<=maX; i+=2)
    {
        marked[i]=1;
    }
    p.push_back(2);
    for(ll i=3; i<=maX; i+=2)
    {
        if(marked[i]==0)
        {
            p.push_back(i);
            if(p.size()>500) break;
            for(ll j=i*i; j<=maX; j+=i+i)
            {
                marked[j]=1;
            }
        }
    }
}

ll dp[505][505];

ll solve(ll pr,ll st)
{
    if(pr<0) return 0;
    if(st==0) return 1;
    if(dp[pr][st]!=-1) return dp[pr][st];

    ll ans=(p[pr]*solve(pr,st-1)%mod + solve(pr-1,st))%mod;

    return dp[pr][st]=ans;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    sieve();

    memset(dp,-1,sizeof dp);
    test
    {
        ll n,m,i,j,k,l;

        cin>>k>>n;

        ll ans=1;

        for(i=0;i<n;i++)
        {
            ans=ans*(p[i]-1);
            ans%=mod;
        }
        ans*=solve(n-1,k-n);
        cout<<"Case "<<cs<<": "<<ans%mod<<nl;
    }
    return 0;
}