Description

slwang 顺利找到了隐藏节点，不甘心的 AsindE 又提出一天后两人以 nim 游戏定胜负。在 nim 游戏中有若干个非空石子堆，AsindE 和 slwang 轮流操作，当前操作的玩家需要选择一个非空石子堆拿走至少一个石子，如果无法操作，则当前操作的玩家失败。

这次 AsindE 让 slwang 先手，但 slwang 不知道的是，石子堆是由 AsindE 设置的。AsindE 共有 $n$ 个石头，他可以将这些石头按顺序分成若干个非空的石子堆，这些石子堆组成一个石子堆序列 $\{a_i\}$ $(1 \leq a_i \leq n;\sum a_i = n)$，第 $i$ 个石子堆有 $a_i$ 个石头。现在 AsindE 想知道在双方每一步都采取最优行动的前提下，有多少种不同的石子堆序列能确保他取得胜利。

当两种石子堆序列 $\{a_i\},\{b_i\}$ 满足以下任意一种情况时，就认为两种石子堆序列不同：

• 两个序列的长度不同；
• 两个序列的长度相同，但存在至少一个位置 $j$ 使得 $a_j \neq b_j$。

例如：序列 $\{1, 1, 3\}$ 与序列 $\{1, 1, 3\}$ 相同，但序列 $\{1, 1, 3\}$ 与 序列 $\{1, 3, 1\}$ 不同，序列 $\{2, 4\}$ 与序列 $\{1, 2, 3\}$ 也不同。

答案可能很大，请将答案对 $998244353$ 取模。

Format

Input

第一行一个正整数 $n$ $(1 \leq n \leq 500)$。

Output

一行一个整数，表示在 slwang 先手的情况下，AsindE 必胜的不同石子堆序列数量对 $998244353$ 取模的结果。

Samples

4

2

12

522

Notes

对于第一个样例共两个序列满足要求：$\{1,1,1,1\}$ 和 $\{2, 2\}$。

Limitation

1s, 1024KiB for each test case.