問題一覧 > 通常問題

No.2079 aaabbc

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

問題文

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

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

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

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

入力

NN

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

    • 出力

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

    サンプル

    サンプル1
    入力
    1
    出力
    3

    (A,B,C)(A,B,C) としてあり得るのは、(1,0,0),(0,1,0),(0,0,1)(1,0,0), (0,1,0), (0,0,1) の 33 つです。 よって答えは、1!1!0!0!+1!0!1!0!+1!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もしくは右上の雲マークをクリックしてアカウントを作成してください。