Посчитайте количество массивов, удовлетворяющих следующим условиям:
- каждый массив состоит из \(n\) элементов;
- каждый элемент — целое число от \(1\) до \(m\);
- в каждом массиве есть ровно одна пара одинаковых элементов;
- в каждом массиве \(a\) существует такой индекс \(i\), что массив строго возрастает до \(i\)-го элемента и строго убывает после него (формально, \(a_j < a_{j + 1}\), если \(j < i\), и \(a_j > a_{j + 1}\), если \(j \ge i\)).
Выходные данные
Выведите одно целое число — количество массивов, удовлетворяющих всем вышеописанным условиям, взятое по модулю \(998244353\).
Примечание
Массивы из первого примера:
- \([1, 2, 1]\);
- \([1, 3, 1]\);
- \([1, 4, 1]\);
- \([2, 3, 2]\);
- \([2, 4, 2]\);
- \([3, 4, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
|
6
|
|
2
|
3 5
|
10
|
|
3
|
42 1337
|
806066790
|
|
4
|
100000 200000
|
707899035
|