← 返回题目列表

AtCoder · agc064_f

F. 无排列

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

分数: 1700 点

问题陈述

给你一个正整数 N。 打印数字,模数 998244353,序列 A 长度 3N 包含来自的每个整数 1 通过 N 三次并满足以下条件。

  • A 没有连续的长度子序列 N 这是序列的排列 (1, 2, \ldots, N).

约束

  • 1 \leq N \leq 2 \times 10^5
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N

输出

打印答案。


示例输入 1

3

示例输出 1

132

例如, A = (1, 3, 3, 2, 2, 2, 1, 1, 3) 满足问题陈述中的条件。 另一方面, A = (1, 3, 3, 2, 2, 3, 1, 1, 2) 不会,因为 5-th, 6-th, 7第一个元素 A 形成一个连续的子序列,它是序列的排列 (1, 2, 3).


示例输入 2

123456

示例输出 2

31984851