問題一覧 > 通常問題

No.2079 aaabbc

レベル : / AI推定難易度 : 475 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 123
作問者 : taiga0629kyopro / テスター : 👑 p-adic 👑 AngrySadEight ygussany
お気に入りにしたユーザー ProblemId : 8481 / 自分の提出
問題文最終更新日: 2022-09-17 20:35:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 361 (順位表) の他の問題:

Problem Statement

Taiga, who is studying mathematics, came across the following problem.

How many ways are there to arrange the $6$ letters a, a, a, b, b, c in $1$ row?

The answer to this problem is $\displaystyle \frac{6!}{3!2!1!}=60$ ways. Now, solve the following problem.

For every tuple of non-negative integers $(A,B,C)$ satisfying $A+B+C=N$, compute $\displaystyle \frac{N!}{A!B!C!}$, and find the sum of these values. Since the answer is an integer, print the answer modulo $998244353$.

Input

$N$

  • $1 \le N \le 10^9$
  • All inputs are integers.

    • Output

    Print the answer modulo $998244353$.

    Sample

    Sample 1
    Input
    1
    Output
    3

    The possible values of $(A,B,C)$ are the $3$ tuples $(1,0,0), (0,1,0), (0,0,1)$. Therefore, the answer is $\frac{1!}{1!0!0!}+\frac{1!}{0!1!0!}+\frac{1!}{0!0!1!}=3$.

    Sample 2
    Input
    62
    Output
    101208447

    Sample 3
    Input
    100
    Output
    578373382

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