本題是一道計分（SCORED）題。共有十個資料子組，各子組將獨立評測。通過某個子組中的所有測試資料將獲得本題 $0.1$ 的分數（計分板上會顯示為 $0.1$，但在 Kattis 的回應中可能會顯示為 $10$）。通過全部十個子組中的所有測試資料將獲得 $1$ 道完整題目的分數。你可以繼續提交程式碼以嘗試提高你的分數。

本題的時間罰時將按以下規則計算：

• 從比賽開始到使你分數增加的最後一次提交為止，每分鐘記一分罰時。

• 在該最後一次增加分數的提交之前，每次未能增加分數的提交記二十分罰時，但編譯錯誤除外（編譯錯誤不計罰時）。

• 如果你的分數始終未超過零，則不計任何罰時。

還記得那首《聖誕節的十二天》（"The 12 Days of Christmas"）嗎？

「在聖誕節的第一天，我的真愛送給我：梨樹上的一隻山鶉。」

太棒了。我本來想要一支 iPhone 的。

「在聖誕節的第二天，我的真愛送給我：兩隻斑鳩，以及梨樹上的一隻山鶉。」

好吧，現在我有四隻鳥了：今天的兩隻斑鳩和一隻山鶉，加上昨天的一隻山鶉。我的貓都要瘋了。

「在聖誕節的第三天，我的真愛送給我：三隻法國母雞、兩隻斑鳩，以及梨樹上的一隻山鶉。」

怎麼全是鳥？今天又多了六隻，所以我現在一共有十隻鳥，而且根本沒地方放（除非塞進貓肚子裡）。我的真愛還能把這件事持續多久？

給定一個整數 $n$，在 $n$ 天之後我一共收到了多少件禮物？由於這個數值可能很大，請將其除以 $998\,244\,353$ 的餘數輸出。

輸入格式

輸入僅一行，包含一個整數 $n$，表示我的真愛送給我禮物的天數。

共有十個資料子組，每個子組對 $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$ 天後我收到的禮物總數。因為這個數可能非常大，請將其除以 $998\,244\,353$ 的餘數輸出。

範例

輸入格式 1

1

輸出格式 1

1

輸入格式 2

2

輸出格式 2

4

輸入格式 3

3

輸出格式 3

10