Score : $600$ points

问题描述

一个正整数序列被称为精彩序列，如果其中任意两个相邻元素都不相等。

找出所有元素和为 $N$ 的精彩序列的长度之和，结果对 $998244353$ 取模。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

A positive-integer sequence is said to be splendid if no two adjacent elements are equal.

Find the sum, modulo $998244353$, of the lengths of all splendid sequences whose elements have a sum of $N$.

Constraints

• $1 \le N \le 2 \times 10^5$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer.

Sample Input 1

4

Sample Output 1

8

There are four splendid sequences whose sum is $4$: $(4),(1,3),(3,1),(1,2,1)$. Thus, the answer is the sum of their lengths: $1+2+2+3=8$.

$(2,2)$ and $(1,1,2)$ also have a sum of $4$ but ineligible because their $1$-st and $2$-nd elements are the same.

Sample Input 2

297

Sample Output 2

475867236

Sample Input 3

123456

Sample Output 3

771773807

update @ 2024/3/10 12:21:11