Маленький Тайлер зашел на кухню и увидел, что на холодильнике магнитиками выложена строка \(s\). Он сразу увидел её безграничный потенциал!
Тайлеру нравятся строки, особенно те, которые лексикографически меньше другой строки \(t\). Играя с магнитиками на холодильнике, он задумался, а сколько различных строк, лексикографически меньших строки \(t\), он может собрать, переставляя буквы в строке \(s\). Так как он учится всего лишь во втором классе, он не может этого посчитать, поэтому просит вас о помощи! Так как в алфавите языка Тайлера много букв, то для вашего удобства Тайлер уже заменил одинаковые буквы в строках \(s\) и \(t\) одинаковыми числами, а разные — разными.
Напомним, что строка \(x\) лексикографически меньше строки \(y\), если выполнено одно из двух условий:
- существует такая позиция символа \(m\), присутствующая в обеих строках, что до \(m\)-го символа строки совпадают, а \(m\)-й символ строки \(x\) меньше \(m\)-го символа \(y\),
- строка \(x\) является префиксом \(y\) и \(x \neq y\).
Так как ответ может быть слишком большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Выведите единственное число — количество строк, лексикографически меньших \(t\), которые можно получить, переставляя буквы в \(s\), по модулю \(998\,244\,353\).
Примечание
В первом примере интересующие нас строки это \([1\, 2\, 2]\) и \([2\, 1\, 2]\). Строка \([2\, 2\, 1]\) лексикографически больше строки \([2\, 1\, 2\, 1]\), поэтому её мы не считаем.
Во втором примере подходят все строки, кроме \([4\, 3\, 2\, 1]\), так что их \(4! - 1 = 23\).
В третьем примере подходит только строка \([1\, 1\, 1\, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 2 2
2 1 2 1
|
2
|
|
2
|
4 4
1 2 3 4
4 3 2 1
|
23
|
|
3
|
4 3
1 1 1 2
1 1 2
|
1
|