← 返回题目列表

AtCoder · arc153_e

E. 双端队列最小化

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

分数: 800 点

问题陈述

对于正整数 X 没有一个数字是 0,考虑获取正整数 Y 如下。

  • 初始化 S 作为空字符串。
  • 让 N 是中的位数 X。对于 i = 1, \ldots, N 按此顺序,执行以下操作:插入 i- 十进制表示法中的第一个字符 X 的开头或结尾 S.
  • 让 Y 是字符串表示的正整数 S.

让 f(X) 表示可以从下式获得的最小正整数 X 这样。


给你一个正整数 Y 没有一个数字是 0。打印数字,模数 998244353,正整数 X 没有一个数字是 0 这样 f(X) = Y.

约束

  • Y 是一个正整数,其数字均不为 0.
  • 1\leq Y < 10^{200000}

输入

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

Y

输出

打印数字,模数 998244353,正整数 X 没有一个数字是 0 这样 f(X) = Y.


样本输入 1

1332

示例输出 1

3

三个整数, 1332, 3132,和 3312,满足条件。


示例输入 2

3312

示例输出 2

0

示例输入 3

12234433442

示例输出 3

153