← 返回题目列表

AtCoder · abc242_c

F. 1111gal密码

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给定一个整数 N,查找整数的个数 X 满足以下所有条件,模 998244353.

  • X 是一个 N- 数字正整数。
  • 让 X_1,X_2,\dots,X_N 是以下数字 X 从上到下。他们满足以下所有条件:
    • 1 \le X_i \le 9 对于所有整数 1 \le i \le N;
    • |X_i-X_{i+1}| \le 1 对于所有整数 1 \le i \le N-1.

约束

  • N 是一个整数。
  • 2 \le N \le 10^6

输入

输入由标准输入按以下格式给出:

N

输出

将答案打印为整数。


示例输入 1

4

示例输出 1

203

一些 4-满足条件的数字整数是 1111,1234,7878,6545.


示例输入 2

2

示例输出 2

25

示例输入 3

1000000

示例输出 3

248860093

一定要找到计数模数 998244353.