← 返回题目列表

AtCoder · abc297_h

Ex. 差异相邻

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

分数: 600 点

问题陈述

正整数序列被称为 精彩 如果没有两个相邻元素相等。

求总和,取模 998244353,其元素总和为的所有精彩序列的长度 N.

约束

  • 1 \le N \le 2 \times 10^5
  • 输入中的所有值都是整数。

输入

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

N

输出

打印答案。


示例输入 1

4

示例输出 1

8

有四个精彩序列,其总和为 4: (4),(1,3),(3,1),(1,2,1)。 因此,答案是它们的长度之和: 1+2+2+3=8.

(2,2) 和 (1,1,2) 还有一笔 4 但没有资格,因为他们 1-st 和 2-nd 元素相同。


示例输入 2

297

示例输出 2

475867236

示例输入 3

123456

示例输出 3

771773807