Все автобусные билеты в Берляндии пронумерованы. Номер каждого билета состоит из \(n\) цифр (\(n\) четно). При этом в номерах билетов могут быть использованы только \(k\) цифр \(d_1, d_2, \dots, d_k\). Допустимо, что номера билетов Берляндии содержат один или более лидирующих нулей, если \(0\) может использоваться в номерах билетов. Например, если \(n = 4\) и в билетах можно использовать две цифры \(0\) и \(4\), то номера \(0000\), \(4004\), \(4440\) могут быть номерами билетов в Берляндии, а номера \(0002\), \(00\), \(44443\) — нет.
Билет в Берляндии считается счастливым, если сумма первых \(n / 2\) цифр равна сумме последних \(n / 2\) цифр.
Определите общее количество счастливых билетов в Берляндии. Так как это число может быть очень большим, выведите остаток от деления общего количества счастливых билетов на \(998244353\).
Выходные данные
Выведите остаток от деления общего количества счастливых билетов в Берляндии на \(998244353\).
Примечание
В первом примере всего \(6\) счастливых номеров билетов: \(1111\), \(1818\), \(1881\), \(8118\), \(8181\) и \(8888\).
Во втором примере существует всего один номер билета, который допустим в Берляндии, он состоит из \(20\) цифр \(6\). Этот билет является счастливым, поэтому ответ \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 8
|
6
|
|
2
|
20 1
6
|
1
|
|
3
|
10 5
6 1 4 0 3
|
569725
|
|
4
|
1000 7
5 4 0 1 8 3 2
|
460571165
|