题目描述

给定 $n$，求有多少 $0\sim n$ 的排列 $p_{0\cdots n}$ 满足，对于任意 $0 \leq a<b<c<d \leq n$：

• 若 $a + d = b + c$，则区间 $[\min(p_a, p_d), \max(p_a, p_d)]$ 与 $[\min(p_b, p_c), \max(p_b, p_c)]$ 包含或不交。

答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

输出格式

一行一个整数表示答案。

4

30

数据范围

对于所有数据，保证 $2\leq n \leq 10^{10}$。

• 测试点 $1, 2$，保证 $n \leq 10$。
• 测试点 $3 \sim 5$，保证 $n \leq 20$。
• 测试点 $6 \sim 8$，保证 $n \leq 50$。
• 测试点 $9 \sim 13$，保证 $n \leq 10^6$。
• 测试点 $14 \sim 17$，保证 $n \leq 10^9$。
• 测试点 $18 \sim 20$，无特殊限制。

samples

solution