問題一覧 > 通常問題

No.2137 Stairs of Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : taiga0629kyopro / テスター : kaichou243
0 ProblemId : 8726 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-25 02:45:26

問題文

(1,2,…,N)(1,2,\dots,N) の順列 PP に対して f(P)f(P) を次のように定めます。

    f(P)=1≤i≤Nf(P)=1 \le i \le N かつ max⁡(P1,P2,…,Pi)=Pi\max(P_1,P_2,\dots,P_i)=P_i となる整数 ii の個数

(1,2,…,N)(1,2,\dots,N) の順列 PP は N!N! 個ありますが、その全てに対する f(P)3f(P)^3 の総和を 998244353998244353 で割った余りを求めてください。

入力

NN

  • 1≤N≤1071 \le N \le 10^7
  • 入力は全て整数

    • 出力

    答えを出力してください。

    サンプル

    サンプル1
    入力
    3
    出力
    53

    f((1,2,3))3+f((1,3,2))3+f((2,1,3))3+f((2,3,1))3+f((3,1,2))3+f((3,2,1))3=33+23+23+23+13+13=53f((1,2,3))^3+f((1,3,2))^3+f((2,1,3))^3+f((2,3,1))^3+f((3,1,2))^3+f((3,2,1))^3=3^3+2^3+2^3+2^3+1^3+1^3=53 です。

    サンプル2
    入力
    100
    出力
    549865790

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