配点 : 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}
小課題
- (50 点) N \leq 8
- (50 点) N \leq 15
- (200 点) N \leq 3000
- (100 点) N \leq 10^6
- (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 约束。