IQ Game
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Популярная телепередача «Как? Зачем? Почему?» показывает, что команда из шести игроков работает вместе над решением сложных вопросов. Игроки сидят за круглым столом, разделенным на $$$n$$$ секторов, пронумерованных по часовой стрелке от $$$1$$$ до $$$n$$$. В начале игры в каждом секторе лежит конверт с вопросом, на который нужно ответить.

Каждый раунд волчок в центре стола равномерно случайным образом выбирает сектор стола. Если в выбранном секторе есть конверт, ведущий открывает его и читает вопрос внутри. Если в выбранном секторе нет конверта, вместо этого открывается следующий конверт по часовой стрелке от выбранного сектора. После раунда вскрытый конверт убирается со стола.

Сегодня играет любимая команда зрителей. Они уже сыграли $$$n - k$$$ раундов из $$$n$$$, поэтому на столе осталось $$$k$$$ конвертов. Дела у команды идут неважно — еще один неверный ответ отправит их домой. Один из вопросов — это особый, печально известный сложный вопрос, который называется «Гиперблиц». Команда уверена, что сможет ответить на все оставшиеся вопросы, кроме "Гиперблиц". Найдите ожидаемое количество раундов, которые они сыграют, по модулю $$$998\,244\,353$$$ (подробности см. в разделе «Вывод»).

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$k$$$ и $$$s$$$  — общее количество секторов, количество оставшихся вопросов и сектор, содержащий вопрос "гиперблиц" ($$$1 \le n \le 10^9$$$; $$$1 \le k \le \min(n, 200)$$$; $$$1 \le s \le n$$$). Гарантируется, что $$$n$$$ не равно $$$998\,244\,353$$$.

Вторая строка содержит $$$k$$$ различных целых чисел $$$q_1, q_2, \ldots , q_k$$$  — номера секторов, которые еще имеют оболочки, в порядке по часовой стрелке ($$$1 \le q_1 < q_2 < \ldots < q_k \le n $$$).

Существует ровно один индекс $$$i$$$ с $$$q_i = s$$$.

Выходные данные

Выведите одно целое число — ожидаемое количество раундов, которое команда сыграет (включая неизбежный "Гиперблиц"), по модулю $$$998\,244\,353$$$.

Формально пусть $$$M = 998\,244\,353$$$. Можно показать, что ожидаемое количество раундов можно выразить в виде неприводимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, а $$$q \not \equiv 0 \pmod{M }$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Примеры

Входные данные
3 2 3
2 3
Выходные данные
665496237
Входные данные
6 3 4
1 2 4
Выходные данные
582309208
Входные данные
8 8 5
1 2 3 4 5 6 7 8
Выходные данные
499122181

Примечание

В первом тестовом примере в первом туре команда играет "Гиперблиц" с вероятностью $$$\frac 13$$$, значит, с вероятностью $$$\frac 13$$$ они играют 1 раунд, а с вероятностью $$$\frac 23$$$ играют 2 раунда. Ожидаемое количество раундов: $$$1 \cdot \frac 13 + 2 \cdot \frac 23 = \frac 53$$$.

Так как $$$3^{-1} \bmod {998\,244\,353} = 332\,748\,118$$$, правильный вывод: $$$5 \cdot 332\,748\,118 \bmod {998\,244\,353} = 665\,496\,237$$$.