1,000,000,007や998,244,353は答えの剰余を取るタイプの問題でよく出てくる数ですね。

① そもそもなぜ剰余を取るのか
② なぜ1,000,000,007がよく使われるのか
③ なぜ998,244,353がよく使われるのか

ということに順にお答えすることで元の質問に対する回答になると思うので、それらについてお答えしますね。

① そもそもなぜ剰余を取るのか

そもそもなぜ剰余を取るのが一般的かというと、組み合わせの数を計算する問題では実際の答えの数が32bitさらには64bitの範囲を超えることが一般的で、それらをちゃんと計算するには多倍長整数を扱わないといけないのですが、残念ながら多倍長整数はそれの計算そのものに時間がかかりすぎたり言語によっては取り扱う標準ライブラリがなかったり、それらを要求すると問題の本当に問いたいことからあまりにもそれてしまうので、答えの剰余を取ったものを計算しようという文化になっています。組み合わせの数の計算過程で逐一問題で指定された数で余りを取ることで常に32bit整数または64bit整数を用いての計算が可能になります。

② なぜ1,000,000,007がよく使われるのか

・足したときに 符号付き32bitを超えない (1,000,000,007 + 1,000,000,007 < 2^31)

・掛け合わせたときに符号付き64bitを超えない。

・素数なので剰余環における割り算が扱いやすい(1<p<1,000,000,007の範囲で常に逆元が存在する)

という性質が上記で述べた多倍長計算を避けるのにちょうどよく、その中でできるだけ大きいものだと嬉しいからです。

③ なぜ998,244,353がよく使われるのか。

これはやや非自明です。組み合わせの数の計算の問題では稀に高速フーリエ変換を用いて計算量を削減する問題が出ます。通常の高速フーリエ変換では複素数をうまく用いるのですが、ある性質を持つ素数を複素数の代わりに使い剰余環上で高速フーリエ変換を可能にした高速剰余変換(FMT)というものが存在します。FMTを想定解にすることで高速フーリエ変換をしてかつ余りを取るといったタイプの問題が出題できるようになります。性質の良い素数として1+a*2^nの形を取りかつnができるだけ大きい素数が挙げられて(そのような形の素数を使うと長さ2^nの列に対するFMTができる)、具体的にな質の良い整数の代表例として998244353=1+119×2^23が挙げられます。上記で述べたちょうど良い大きさの素数という性質を満たしつつ、FMTにも扱えるさらに都合の良い素数ということになります。ただ、完全に問題出題側に都合の良い恣意的な素数設定で、この素数が出た瞬間に解法にFMTが関わっているという推測が容易になってしまうのでとりあえず解法にFMTが必要だろうと必要でなかろうと常にこの素数で出す作問者もいます。

FMTに関する詳細はこちらのSen_comp様のブログが参考になりましたので紹介させていただきます。

https://sen-comp.hatenablog.com/entry/2021/02/06/180310

まとめ

① そもそもなぜ剰余を取るのか　
→多倍長計算を避けて組み合わせの数の計算の問題を面白くするため

② なぜ1,000,000,007がよく使われるのか　
→足して符号付き32 bit intの範囲に収まり掛けて符号付き64bit intの範囲に収まる素数でちょいど良い大きさだから。

③ なぜ998,244,353がよく使われるのか。　
→上記の性質を満たすことに加え高速剰余変換をする際に性質が良いから。ただしこの素数そのものが解法のヒントになることを嫌って高速剰余変換が必要であろうとなかろうと常にこの素数で出す作問者もいる。