이 문제는 점수제(SCORED) 문제입니다. 데이터는 열 개의 소그룹으로 나뉘어 있으며, 각 소그룹은 독립적으로 채점됩니다. 한 소그룹의 모든 데이터를 해결하면 문제 점수의 $0.1$점을 얻습니다(스코어보드에는 그렇게 표시되지만, Kattis의 응답에서는 $10$으로 표시될 수 있습니다). 열 개의 모든 소그룹의 데이터를 모두 해결하면 $1$문제 전체 점수를 얻습니다. 점수를 높이기 위해 계속해서 제출할 수 있습니다.

이 문제의 시간 페널티는 다음과 같이 부과됩니다:

• 대회 시작부터 점수가 증가한 마지막 제출까지 매 1분마다 1점의 페널티가 부과됩니다.

• 점수가 증가한 마지막 제출 이전에 점수를 올리지 못한 각 제출마다 20점의 페널티가 부과됩니다. 단, 컴파일 에러는 예외로 페널티가 부과되지 않습니다.

• 점수가 0점을 초과한 적이 없다면 페널티는 부과되지 않습니다.

"크리스마스의 12일(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