← 返回题目列表

AtCoder · pakencamp_2022_day2_b

B. 成绩

中文机器翻译题面 查看原题

配点 : 500 点

問題文

每年在Parken学园 有 N 个学期。 它的编号为 1, 2, \ldots, N 。每个学期都会给出成绩,成绩为 表示为最大 1 如果要将其更改为输出最多为 N 的整数值。

现在,作为 Paken Gakuen 的学生,您在年底查看每个学期的成绩。然后我注意到以下几点。这里 i 第学期成绩 比方说 G_i 。 它是

  • G 是长度 它是一个 N 的排列。
  • 2 有些学期的成绩低于上学期,并且这些学期是连续的。 1 有两个部分。

此时,满足这些条件的成绩 查找 G_1, G_2, \ldots, G_N 的编号。然而,答案可能非常大,所以 请打印除以 998244353 后的余数。

制約

  • 所有输入均为整数
  • 2 \leq N \leq 10^{18}

小課題

  1. (50 点) N \leq 8
  2. (50 点) N \leq 15
  3. (200 点) N \leq 3000
  4. (100 点) N \leq 10^6
  5. (100 点)无附加约束

入力

输入将以以下形式通过标准输入给出。

N

出力

答案 打印除以 998244353 后的余数。


入力例 1

4

出力例 1

18

是一个排列 G , G_1 < G_2 < G_3 < G_4 和 仅当 G_1 > G_2 < G_3 > G_4 时,不满足条件。

这样的 G 是 (1, 2, 3, 4), (2, 1, 4, 3), (3, 1, 4, 2), (3, 2, 4, 1), (4, 1, 3, 2), (4, 2, 3, 1) 的 6 有一个。长度 4 的排列是 有 24 ,所以答案是 18 。

此输入满足所有子任务约束。


入力例 2

13

出力例 2

398574

此输入是一个小作业 满足 2, 3, 4, 5 约束。


入力例 3

2947

出力例 3

663703367

此输入是一个小作业 满足 3, 4, 5 约束。


入力例 4

999999

出力例 4

946508973

此输入是一个小作业 满足 4, 5 约束。


入力例 5

1000000000000000000

出力例 5

856673235

此输入是一个小作业 满足 5 约束。