Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
先頭の桁が 0 でない N 桁の正整数 A,B が与えられます。
あなたは、以下の操作を好きな回数(0 回でもよい)繰り返すことができます。
- 0 \le i \le N-1 を満たす整数 i を選び、A,B の 10^{i} の位の数字を交換する。
操作を終えたときの A \times B の最小値を 998244353 で割ったあまりを求めてください。
A \times B を 998244353 で割ったあまりの最小値を求めるのではないことに注意してください。
制約
- 1 \le N \le 200000
- A,B は先頭の桁が 0 でない N 桁の正整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
答えを 1 行に出力せよ。
入力例 1
2 13 22
出力例 1
276
以下のように 1 回操作を行うと A \times B を 276 にすることが出来ます。
- i=0 を選び、A,B の 1 の位の数字を交換する。A=12,B=23 となる。
A \times B を 275 以下にすることは出来ないので、答えは 276 です。
入力例 2
8 20220122 21002300
出力例 2
54558365
998244353 で割ったあまりを求めてください。
Score : 300 points
Problem Statement
You are given N-digit positive integers A and B whose topmost digits are not 0.
You can repeat the following operation any number of times (possibly zero).
- Choose an integer i such that 1 \le i \le N and swap the i-th lowest digits of A and B.
Find the smallest possible value of A \times B after your operations, modulo 998244353.
Note that you are not asked to minimize the remainder when A \times B is divided by 998244353.
Constraints
- 1 \le N \le 200000
- A and B are N-digit positive integers whose topmost digits are not 0.
Input
The input is given from Standard Input in the following format:
N A B
Output
Print a single line containing the answer.
Sample Input 1
2 13 22
Sample Output 1
276
You can make A \times B = 276 by performing the operation once, as follows.
- Choose i=1 to swap the bottommost digits of A and B, making A=12, B=23.
You cannot make A \times B = 275 or less, so the answer is 276.
Sample Input 2
8 20220122 21002300
Sample Output 2
54558365
Find the value modulo 998244353.