

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正の整数 A_{1}, A_{2}, A_{3} が与えられます。 以下の条件を全て満たす正の整数の組 (X_{1}, X_{2}, X_{3}) の場合の数を 998244353 で割ったあまりを求めてください。
- X_{1} は 10 進法で A_{1} 桁の正の整数
- X_{2} は 10 進法で A_{2} 桁の正の整数
- X_{3} は 10 進法で A_{3} 桁の正の整数
- X_{1} + X_{2} = X_{3}
1 つの入力ファイルにつき T 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- 1\leq T\leq 10^{5}
- 1\leq A_{i}\leq 10^{9}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
T \text{case}_{1} \text{case}_{2} \vdots \text{case}_{T}
各ケースは以下の形で与えられます。
A_{1} A_{2} A_{3}
出力
T 行出力してください。i 行目には \text{case}_{i} に対する答えを出力してください。
入力例 1
4 1 1 1 1 6 7 167 167 167 111 666 777
出力例 1
36 45 731780675 0
1 つ目のケースについて、(X_{1}, X_{2}, X_{3}) = (1, 6, 7), (2, 1, 3) などが条件を満たします。
(X_{1}, X_{2}, X_{3}) = (6, 7, 13), (3, 4, 5) などは条件を満たしません。
条件を満たす (X_{1}, X_{2}, X_{3}) の組は 36 通りあるので 36 を出力してください。
3 つ目のケースについて、答えを 998244353 で割ったあまりを出力することに注意してください。
4 つ目のケースについて、条件を満たす (X_{1}, X_{2}, X_{3}) の組が存在しないこともあります。
Score : 600 points
Problem Statement
You are given positive integers A_{1}, A_{2}, A_{3}. Find the number, modulo 998244353, of tuples of positive integers (X_{1}, X_{2}, X_{3}) that satisfy all of the following conditions.
- X_{1} is a positive integer with A_{1} digits in decimal notation.
- X_{2} is a positive integer with A_{2} digits in decimal notation.
- X_{3} is a positive integer with A_{3} digits in decimal notation.
- X_{1} + X_{2} = X_{3}.
You are given T test cases per input file; solve each of them.
Constraints
- 1 \leq T \leq 10^{5}
- 1 \leq A_{i} \leq 10^{9}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T \text{case}_{1} \text{case}_{2} \vdots \text{case}_{T}
Each case is given in the following format:
A_{1} A_{2} A_{3}
Output
Print T lines. The i-th line should contain the answer for \text{case}_{i}.
Sample Input 1
4 1 1 1 1 6 7 167 167 167 111 666 777
Sample Output 1
36 45 731780675 0
For the first case, tuples such as (X_{1}, X_{2}, X_{3}) = (1, 6, 7), (2, 1, 3) satisfy the conditions.
On the other hand, tuples such as (X_{1}, X_{2}, X_{3}) = (6, 7, 13), (3, 4, 5) do not.
There are 36 tuples (X_{1}, X_{2}, X_{3}) that satisfy the conditions, so print 36.
For the third case, remember to print the result modulo 998244353.
For the fourth case, there may be no tuples (X_{1}, X_{2}, X_{3}) that satisfy the conditions.