#P15523. [HNOI2026省队集训]箴言(aphorism)

[HNOI2026省队集训]箴言(aphorism)

题目描述

给定 nn,求有多少 0∼n0\sim n 的排列 p0⋯np_{0\cdots n} 满足,对于任意 0≤a<b<c<d≤n0 \leq a<b<c<d \leq n:

  • 若 a+d=b+ca + d = b + c,则区间 [min⁡(pa,pd),max⁡(pa,pd)][\min(p_a, p_d), \max(p_a, p_d)] 与 [min⁡(pb,pc),max⁡(pb,pc)][\min(p_b, p_c), \max(p_b, p_c)] 包含或不交。

答案对 998244353998244353 取模。

输入格式

第一行一个正整数 nn。

输出格式

一行一个整数表示答案。

输入数据 1

4

[Copy](javascript:;)

输出数据 1

30

[Copy](javascript:;)

数据范围

对于所有数据,保证 2≤n≤10102\leq n \leq 10^{10}。

  • 测试点 1,21, 2,保证 n≤10n \leq 10。
  • 测试点 3∼53 \sim 5,保证 n≤20n \leq 20。
  • 测试点 6∼86 \sim 8,保证 n≤50n \leq 50。
  • 测试点 9∼139 \sim 13,保证 n≤106n \leq 10^6。
  • 测试点 14∼1714 \sim 17,保证 n≤109n \leq 10^9。
  • 测试点 18∼2018 \sim 20,无特殊限制。

samples

solution