/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N, M が与えられます。
正整数 d に対し、d 桁の repunit を整数 \displaystyle\sum_{i = 0}^{d - 1} 10^i として定義します。
相異なるとは限らない 1 桁以上 M 桁以下の repunit N 個の和として表すことのできる整数の個数を 998244353 で割った余りを求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
2 3
出力例 1
6
1 桁以上 3 桁以下の repunit は 1, 11, 111 の 3 つです。これら 2 つの和として表すことのできる整数は 2, 12, 22, 112, 122, 222 の 6 つです。
入力例 2
10 10
出力例 2
92378
入力例 3
12345 123456789
出力例 3
133394021
Score : 600 points
Problem Statement
You are given positive integers N, M.
For a positive integer d, define the repunit with d digits as the integer \displaystyle\sum_{i = 0}^{d - 1} 10^i.
Find the number, modulo 998244353, of integers that can be expressed as the sum of (not necessarily distinct) N repunits, each with at least 1 digit and at most M digits.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Output the answer.
Sample Input 1
2 3
Sample Output 1
6
We have 3 repunits with at least 1 digit and at most 3 digits: 1, 11, 111. As the sum of 2 of them, we can express 6 integers: 2, 12, 22, 112, 122, 222.
Sample Input 2
10 10
Sample Output 2
92378
Sample Input 3
12345 123456789
Sample Output 3
133394021