Problem Description

There are $ N $ people numbered from $ 1 $ to $ N $. Person $ i $ wears a jersey with an integer $ B_i $ written on it.

There are $ N! $ ways to arrange these $ N $ people in a single row. For each arrangement, calculate the score defined below and find the sum of all scores modulo $ 998244353 $.

• Let $ A_i $ be the integer written on the jersey of the person in the $ i $-th position from the left. Define $ f(i,j) $ as $ S_{j-i} $ if $ A_j - A_i = j - i $, otherwise $ 0 $. The score is the sum of $ f(i,j) $ for all pairs $ (i,j) $ such that $1 \leq i < j \leq N$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ B_1 $ $\ldots$ $ B_N $ $ S_1 $ $\ldots$ $ S_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
3 2 1
1 10 100

Sample Output #1

14

Sample Input #2

3
3 3 1
1 10 100

Sample Output #2

20

Sample Input #3

9
3 1 4 15 9 2 6 5 35
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output #3

146471953

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq B_i \leq 10^5$
• $1 \leq S_i \leq 998244352$
• All values in the input are integers.

Sample Explanation 1

• When arranging people from left to right as $ 1,2,3 $, $ A = (3,2,1) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 1,3,2 $, $ A = (3,1,2) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 1 = 1 $
• When arranging people from left to right as $ 2,1,3 $, $ A = (2,3,1) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 1 + 0 + 0 = 1 $
• When arranging people from left to right as $ 2,3,1 $, $ A = (2,1,3) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 3,1,2 $, $ A = (1,3,2) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 3,2,1 $, $ A = (1,2,3) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 1 + 10 + 1 = 12 $

Thus, the answer is $ 0 + 1 + 1 + 0 + 0 + 12 = 14 $.

Sample Explanation 2

• When arranging people from left to right as $ 1,2,3 $, $ A = (3,3,1) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 1,3,2 $, $ A = (3,1,3) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 2,1,3 $, $ A = (3,3,1) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 2,3,1 $, $ A = (3,1,3) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 0 + 0 = 0 $
• When arranging people from left to right as $ 3,1,2 $, $ A = (1,3,3) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 10 + 0 = 10 $
• When arranging people from left to right as $ 3,2,1 $, $ A = (1,3,3) $, and the score is $ f(1,2) + f(1,3) + f(2,3) = 0 + 10 + 0 = 10 $

Thus, the answer is $ 0 + 0 + 0 + 0 + 10 + 10 = 20 $.

Sample Explanation 3

Find the sum modulo $ 998244353 $.

见题面 Input 部分

见题面 Output 部分