Вам дана перестановка \(a\) длины \(n\). Напомним, что перестановкой называется массив из \(n\) различных чисел от \(1\) до \(n\) в произвольном порядке.
Ваша сила равна \(s\). Вы можете выполнить \(n\) операций с перестановкой \(a\). \(i\)-я операция состоит в следующем:
- Выберите два значения \(x\) и \(y\) такие, что \(i \leq x \leq y \leq \min(i+s,n)\), и поменяйте местами числа \(x\) и \(y\) в перестановке \(a\). Обратите внимание, что вы можете выбрать \(x=y\), в таком случае обмена не произойдет.
Вы хотите превратить \(a\) в другую перестановку \(b\) после \(n\) операций. Однако некоторые элементы \(b\) отсутствуют и заменены на \(-1\). Вычислите количество способов заменить каждую \(-1\) в \(b\) на некоторое целое число от \(1\) до \(n\) так, чтобы \(b\) была перестановкой, и можно было превратить \(a\) в \(b\) силой \(s\).
Так как ответ может быть большим, выведите его по модулю \(998\,244\,353\).
Примечание
В первом примере \(a=[2,1,3]\). Существуют два способа заменить \(-1\), чтобы \(b\) стала перестановкой: \([3,1,2]\) и \([3,2,1]\). Перестановку \(a\) можно превратить в \([3,1,2]\) силой \(1\) следующим образом: \(\)[2,1,3] \xrightarrow[x=1,\,y=1]{} [2,1,3] \xrightarrow[x=2,\,y=3]{} [3,1,2] \xrightarrow[x=3,\,y=3]{} [3,1,2].\(\) Можно показать, что невозможно превратить \([2,1,3]\) в \([3,2,1]\) силой \(1\). Поэтому только одна перестановка \(b\) подходит, поэтому ответ \(1\).
Во втором примере \(a\) и \(b\) такие же, как в предыдущем примере, но теперь у нас сила \(2\). Перестановку \(a\) можно превратить в \([3,2,1]\) силой \(2\) следующим образом: \(\)[2,1,3] \xrightarrow[x=1,\,y=3]{} [2,3,1] \xrightarrow[x=2,\,y=3]{} [3,2,1] \xrightarrow[x=3,\,y=3]{} [3,2,1].\(\) Можно также превратить \(a\) в \([3,1,2]\) используя силу \(1\) как раньше, поэтому ответ \(2\).
В третьем примере есть только одна перестановка \(b\). Можно показать, что невозможно превратить \(a\) в \(b\), поэтому ответ \(0\).