問題文

正整数 N, M および、長さ N の正整数列 a, b が与えられます。 \sum\limits_{k=1}^N \sum\limits_{x=1}^M (a_k x^k + b_k k^x) を 998244353 で割った余りを求めてください。

制約

• 1 \leq N \leq 200{,}000
• 1 \leq M \leq 10^{18}
• 1 \leq a_k \leq 10^{9}
• 1 \leq b_k \leq 10^{9}
• 入力はすべて整数

小課題

1. (1 点) N \leq 100
2. (1 点) N \leq 5{,}000
3. (98 点) 追加の制約はない

入力例 1

3 2
2 1 7
5 4 2

出力例 1

132

答えは (2 \times 1^1+5 \times 1^1) + (2 \times 2^1+5 \times 1^2) + (1 \times 1^2+4 \times 2^1) + (1 \times 2^2+4 \times 2^2) + (7 \times 1^3+2 \times 3^1) + (7 \times 2^3+2 \times 3^2) = 132 です。

このテストケースは小課題 1, 2 の制約を満たします。

入力例 2

5 123456789012345678
180484765 48450102 509940465 587404308 566608826
261439033 751569102 489070200 768834397 292361745

出力例 2

449755530

このテストケースは小課題 1, 2 の制約を満たします。