OMC182(F)

点数: 600

Writer: imabc

　正の整数 $n$ に対し，正の整数 $f(n)$ を $$f(n)=\sum_{k=1}^{n}\gcd(k,n)$$ により定義します．このとき， $$\mathrm{ord}_2(f(n))=2^{2023}+2056$$ を満たす正の整数 $n$ のうち $10000$ 番目に小さいものを $M$ とします．$M$ は正の奇数 $a$ と非負整数 $b$ を用いて $a\times2^b$ と一意に表せるので，$a+b$ を素数 $1009$ で割ったあまりを求めてください．
　ただし，正の整数 $\ell, m$ に対し，$\gcd(\ell, m)$ は $\ell$ と $m$ の最大公約数を，$\mathrm{ord}_p(m)$ は $m$ が素数 $p$ で割り切れる最大の回数をそれぞれ表します．