この問題は得点制（SCORED）の問題です。データは 10 個のサブグループに分かれており、各サブグループは独立に採点されます。1 つのサブグループ内のすべてのデータを正解すると、問題の $0.1$ 分を獲得します（スコアボード上ではそのように表示されますが、Kattis の応答では $10$ と表示される場合があります）。10 個すべてのサブグループの全データを正解すると、$1$ 問分の満点を獲得します。スコアを伸ばすために何度でも提出を続けることができます。

この問題の時間ペナルティは次のように計算されます：

• コンテスト開始から、スコアが増加した最後の提出までの経過時間 1 分につき 1 点。

• スコアが増加した最後の提出より前に行われた、スコアが増加しなかった提出 1 回につき 20 点（ただしコンパイルエラーは除き、ペナルティは課されません）。

• スコアが一度も 0 を超えなかった場合、ペナルティは課されません。

「クリスマスの12日（"The 12 Days of Christmas"）」という歌を覚えていますか？

「クリスマスの1日目に、私の恋人がくれたもの、梨の木にいるヤマウズラ1羽。」

最高だね。本当は iPhone が欲しかったんだけど。

「クリスマスの2日目に、私の恋人がくれたもの、キジバト2羽、そして梨の木にいるヤマウズラ1羽。」

なるほど、これで鳥が4羽になった。今日のキジバト2羽とヤマウズラ1羽、それに昨日のヤマウズラ1羽だ。うちの猫たちが大騒ぎしている。

「クリスマスの3日目に、私の恋人がくれたもの、フランスのめんどり3羽、キジバト2羽、そして梨の木にいるヤマウズラ1羽。」

いったい鳥ばかりどうなっているんだ？今日はさらに6羽増えて、合計10羽になってしまったし、置く場所もどこにもない（猫のお腹の中を除けば）。恋人はいつまでこれを続けるつもりなんだろう？

整数 $n$ が与えられたとき、$n$ 日後に私が受け取ったプレゼントは合計でいくつになりますか？この値は大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

入力は1行のみで、恋人が私にプレゼントをくれる日数を表す整数 $n$ が与えられます。

データは10個のサブグループに分かれており、それぞれ $n$ の上限が異なります：

1. ($1 \le n \le 10$)

2. ($10 < n \le 1\,000$)

3. ($1\,000 < n \le 10^5$)

4. ($10^5 < n \le 10^7$)

5. ($10^7 < n \le 10^9$)

6. ($10^9 < n \le 10^{11}$)

7. ($10^{11} < n \le 10^{13}$)

8. ($10^{13} < n \le 10^{15}$)

9. ($10^{15} < n \le 10^{17}$)

10. ($10^{17} < n \le 10^{18}$)

出力

ちょうど $n$ 日後に私が受け取るプレゼントの総数を表す1つの整数を出力してください。この数は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入出力例

入力例 1

1

出力例 1

1

入力例 2

2

出力例 2

4

入力例 3

3

出力例 3

10