火星花样滑冰联合会为将于 8 月 31 日在 Matrozavodsk 举行的火星花样滑冰锦标赛通过了新规则。

每位参赛者的节目由一系列跳跃组成。火星人可以完成四种跳跃：Axel、Flip、Lutz 和 Salchow。如果节目满足以下条件，裁判就会认为该节目是优美的（beautiful）。在所有描述中，“任意数量的跳跃”意味着 0 个或多个跳跃。

• 一个优美节目（beautiful program）是一个优秀序列（good sequence）。
• 一个优秀序列（good sequence）以任意数量的 Axel 跳开始。在此之后，该序列可以结束，或者可以继续进行一个 Flip 跳，后面紧跟一个浪漫序列（romantic sequence）或一个活力序列（energetic sequence）。
• 一个浪漫序列（romantic sequence）以任意数量的 Flip 跳或 Lutz 跳（不一定全部相同）开始，后面紧跟：
  • 一个 Lutz 跳或一个 Salchow 跳，然后是一个活力序列（energetic sequence）；或者
  • 一个 Axel 跳，然后是一个优秀序列（good sequence）。
• 一个活力序列（energetic sequence）以任意数量的 Flip 跳开始，后面紧跟一个 Salchow 跳，然后是一个悲剧序列（tragic sequence）。
• 一个悲剧序列（tragic sequence）以任意数量的 Flip 跳开始，后面紧跟：
  • 一个 Axel 跳，然后是一个浪漫序列（romantic sequence）；或者
  • 一个 Axel 跳或一个 Salchow 跳，然后是一个活力序列（energetic sequence）。

规则如此复杂，以至于裁判们想知道有多少种不同的方法可以创造出恰好包含 $n$ 个跳跃的优美节目。请帮助他们解决这个问题。由于答案可能非常大，请将结果模 $998\,244\,353$ 后输出。

输入格式

输入包含多组测试数据。

每组测试数据包含单行，其中有一个整数 $n$（$1 \le n \le 10^9$）。

最后一组测试数据后面紧跟一行，包含一个单独的零。

最多有 $1000$ 组测试数据。

输出格式

对于每组测试数据，输出一个整数，表示可以构成优美节目的跳跃序列数量。

输出答案模 $998\,244\,353$ 的结果。

样例

输入样例 1

1
2
3
4
5
0

输出样例 1

1
2
5
14
42

说明

有 5 个包含 3 个跳跃的序列可以构成优美节目：(Axel, Axel, Axel)；(Axel, Flip, Axel)；(Flip, Axel, Axel)；(Flip, Flip, Axel)；(Flip, Lutz, Axel)。