状態数が少ないのがkey. 値として現れるのは\(1 \leq 2^{a} 3^{b} 5^{c} \leq N\)の形のみ．
値\(x\)に対する答えを\(dp_{x}\)とおく． 遷移を考える． \(x\)のケースが\(ix\,(2 \leq i \leq 6)\)に寄与するのは， \(\frac{1}{6} + \frac{1}{6^2} + \frac{1}{6^3} + \cdots = \frac{1}{5} \). よって，遷移は $$dp_{ix} += dp_{x}/5$$ の配るDPで可能． 初期値は\(dp_{1} = 1\).
この遷移は，直観的にも納得できる． \(1\)の目が出ても最終結果に影響しないから， \(2, \cdots, 6\) の \(5\) 通りしか出ないサイコロで考えているのと同じ．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
map<ll,mint> dp;
set<ll> st;
st.insert(1);
dp[1] = 1;
for(auto x: st){
srep(i,2,7)if(i*x <= n){
dp[i*x] += dp[x] / mint(5);
st.insert(i*x);
}
}
cout << dp[n].val() << endl;
return 0;
}
