問題一覧 > 通常問題

No.2079 aaabbc

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 115
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : 👑 p-adicp-adic 👑 AngrySadEightAngrySadEight 👑 ygussanyygussany
1 ProblemId : 8481 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-17 20:35:35

問題文

数学を勉強している taiga 君は次のような問題に出会いました。

a, a, a, b, b, c の $6$ 個の文字を $1$ 列に並べるとき、並べ方は何通りあるか？

この問題の答えは、$\displaystyle \frac{6!}{3!2!1!}=60$ 通りです。では、次の問題を解いてください。

$A+B+C=N$ を満たす任意の非負整数の組 $(A,B,C)$ について $\displaystyle \frac{N!}{A!B!C!}$ を計算し、その総和を求めてください。なお、答えは整数になるので、答えを $998244353$ で割った余りを出力してください。

入力

$N$

  • $1 \le N \le 10^9$
  • 入力は全て整数。

    • 出力

    答えを $998244353$ で割った余りを出力してください。

    サンプル

    サンプル1
    入力
    1
    出力
    3

    $(A,B,C)$ としてあり得るのは、$(1,0,0), (0,1,0), (0,0,1)$ の $3$ つです。 よって答えは、$\frac{1!}{1!0!0!}+\frac{1!}{0!1!0!}+\frac{1!}{0!0!1!}=3$ となります。

    サンプル2
    入力
    62
    出力
    101208447

    サンプル3
    入力
    100
    出力
    578373382

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。