\(2^k\) команд участвуют в плей-офф турнире. Команды пронумерованы от \(1\) до \(2^k\) в порядке убывания силы. То есть, команда \(1\) самая сильная, команда \(2^k\) самая слабая. Команда с меньшим номером всегда побеждает команду с большим номером.
Сначала все команды располагаются в каком-то порядке. Каждой команде дается еще одно уникальное число от \(1\) до \(2^k\), называемое сид, которое обозначает ее стартовую позицию в плей-офф.
Турнир состоит из \(2^k - 1\) игры. Они проводятся следующим образом: во-первых, команды делятся на пары: команда с сидом \(1\) играет против команды с сидом \(2\), команда с сидом \(3\) играет против команды с сидом \(4\) (именно в таком порядке) и так далее (таким образом, в этой фазе будет сыграно \(2^{k-1}\) игры). Когда команда проигрывает игру, она выбывает.
После этого остается \(2^{k-1}\) команд. Если остается только одна команда, она объявляется чемпионом; в противном случае играется еще \(2^{k-2}\) игр: в первой из них победитель игры «сид \(1\) против сид \(2\)» играет против победителя игры «сид \(3\) против сид \(4\)», затем победитель игры «сид \(5\) против сид \(6\)» играет против победителя игры «сид \(7\) против сид \(8\)» и так далее. Этот процесс повторяется до тех пор, пока не останется только одна команда.
Место команды в турнире зависит от того, в какой фазе турнира она выбыла:
- команда-победитель турнира занимает место \(1\);
- команда, выбывшая в финале, занимает место \(2\);
- обе команды, выбывшие в полуфинале, занимают место \(3\);
- все команды, выбывшие в четвертьфинале, занимают место \(5\);
- все команды, выбывшие в 1/8 финала, занимают место \(9\), и так далее.
Теперь, когда мы установили правила, мы немножко подтасуем результаты. В частности, мы хотим, чтобы:
- команда \(1\) (не команда с сидом \(1\)) заняла место \(1\);
- команда \(2\) заняла место \(2\);
- команды \(3\) и \(4\) заняли место \(3\);
- команды с \(5\) по \(8\) заняли место \(5\), и так далее.
Например, на этой картинке показан возможный ход турнира при \(k = 3\), а также итоговые места команд при таком ходе турнира:
Некоторые сиды уже зарезервированы для некоторых команд (оказывается, не одни мы пытаемся повлиять на результаты). Требуется заполнить оставшиеся сиды оставшимися командами так, чтобы получить желаемые места для команд. Сколько есть способов это сделать? Так как это число может быть довольно большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — количество способов заполнить незарезервированные сиды так, чтобы турнир прошел как мы хотим, по модулю \(998\,244\,353\).