Math String

시간 제한2초메모리 제한1024 MB

요약

숫자 1부터 9와 연산자 +, *로 이루어진 길이 N의 문자열 중 올바른 수식이 되는 모든 문자열의 값을 998244353으로 나눈 나머지의 합을 구한다. N은 최대 10^18이다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 수학, 조합론, 행렬
정답자: 아직 제출이 없습니다

문제

11개의 문자 '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '*'로 이루어진 길이 $N$ 의 문자열 $S$ 를 생각하자.

문자열 $S$ 가 math string이라 함은 다음을 만족한다는 것이다.

$S$ 의 첫 문자와 마지막 문자는 '+'도 '*'도 아니다.
$S$ 에서 연속한 두 문자를 택했을 때, 둘 중 적어도 하나는 '+'도 '*'도 아니다.

각 math string은 십진 표기법으로 쓰인 정수와 일반적인 사칙연산으로 이루어진 산술식으로 볼 수 있으며, 곱셈이 덧셈보다 우선한다. 각 식의 값은 계산할 수 있다. 예를 들어 math string "35+2*6"의 값은 $47$ 이다. 주어진 길이 $N$ 의 모든 math string의 값의 합을 $998\,244\,353$ 으로 나눈 나머지를 구하라.

입력

입력은 정수 $N$ 하나로 이루어진다. ( $1 \le N \le 10^{18}$ )

출력

문제의 답을 정수 하나로 출력한다.

힌트

예제 1에서 서로 다른 한 자리 math string은 '1'부터 '9'까지의 숫자 9개뿐이다. 이 숫자들을 산술식으로 볼 때 그 합은 $45$ 이다.

예제3

예제 1
입력
```
1
```
예상 출력
```
45
```
예제 2
입력
```
3
```
예상 출력
```
407430
```
예제 3
입력
```
1000000000000000000
```
예상 출력
```
493565653
```