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

В первой строке даны целые числа w и K, разделённые пробелом. ($1 \le w \le 60$; $1 \le K \le 100\,000$)

Во второй строке дана длина N имени файла A, которое нужно найти. ($1 \le N \le 100\,000$)

В третьей строке даны элементы A_i ($1 \le i \le N$) через пробел.

Гарантируется, что файл с именем A существует после $K$ операций копирования-вставки.

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

Считая, что самый первый в лексикографическом порядке файл имеет номер $1$, выведите остаток от деления порядкового номера A на $998\,244\,353$.

Примеры

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

2 2
3
0 0 0

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

3

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

2 2
1
3

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

10

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

60 2024
4
998244353 1000000007 3141592653 2718281828

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

62474228

Примечание

Последовательность $a = [a_1, a_2, \cdots, a_n]$ считается лексикографически меньшей, чем последовательность $b = [b_1, b_2, \cdots, b_m]$, если существует такое положительное целое $i$, что выполняются все следующие условия:

• Для всех положительных целых $j < i$ существуют и $a_j$, и $b_j$, причём $a_j = b_j$
• $b_i$ существует
• $a_i$ не существует или $a_i < b_i$