Перед тем, как вся история с украденными молниями Зевса началась, Перси, конечно же, должен был как-то узнать о своем происхождении и вообще о богах Олимпа, а также о том, что древнегреческие боги и чудовища существуют в реальном мире.

Про богов Олимпа Перси впервые узнал из книги, подаренной ему еще совсем в детстве. В ней на одной из иллюстраций все $$$n$$$ богов были расположены в ряд, и снизу было подписано, что сила $$$i$$$-го бога равна $$$a_i$$$. Назовем диссонансом в этом ряду максимальную абсолютную разницу между силой соседних богов, то есть $$$$$$D = \max\limits_{i=1}^{n-1}(|a_i - a_{i+1}|) \text{.}$$$$$$

Сейчас, когда Перси поближе познакомился с богами и остальными существами, он стал уверен, что в книге была опечатка. Поскольку книга все-таки серьезная, опечатка могла быть только одна, и при этом Перси считает, что если ее исправить, то есть изменить какое-то одно $$$a_i$$$ на другое целое число, значение диссонанса $$$D$$$ станет минимально возможным.

Помогите Перси определить, какое $$$a_i$$$ надо исправить, чтобы добиться минимального значения диссонанса в ряду богов Олимпа.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

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

Собственно, этот самый разговор представляет из себя строку $$$s$$$, из которой мы для упрощения удалим все лишние символы, чтобы остались только маленькие буквы латинского алфавита. Когда Перси пересказал этот разговор Аннабет и Гроуверу, у них родились свои догадки о спрятанной в этом разговоре нужной друзьям информации. Аннабет и Гроувер считают, что строка $$$t$$$ может быть скрытым посланием из этого сна, если может быть получена из $$$s$$$ с помощью применения к $$$s$$$ определенной операции некоторое количество раз (ноль или больше).

Эта операция заключается в удалении из $$$s$$$ символа, стоящего на любой четной позиции. Например, из строки «thunder» можно сначала получить «tunder» удалением 'h' на позиции $$$2$$$, затем «tunde» удалением 'r' на позиции $$$6$$$, и затем «tune» удалением 'd' на позиции $$$4$$$. Заметьте, что номер позиции в каждый момент времени считается относительно текущей строки $$$s$$$, а не изначальной.

Для данных строк $$$s$$$ и $$$t$$$ определите, могла ли $$$t$$$ быть получена из $$$s$$$ описанным образом, или догадки ребят неверны.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

You are playing a game of "chaos dice". According to the rules of the game, players take turns rolling $$$k$$$-sided dice and write down the sequence of numbers $$$a_i$$$ that appear on them (numbered from $$$1$$$) until the sequence becomes of length $$$n$$$ ($$$n$$$ is odd).

Lets denote the central index of the sequence as $$$c$$$, i.e., $$$c = \frac{n+1}{2}$$$. You win only if the sequence satisfies the following three criteria:

1. the number $$$k$$$ appears only once and is exactly in the middle of the sequence; more formally — $$$a_c = k$$$ and $$$a_i \ne k$$$ for all $$$i \ne c$$$;
2. the numbers on one side of the center at distances differing by a factor of two are the same; that is, for any $$$d$$$ from $$$-\left\lfloor\frac{c-1}{2}\right\rfloor$$$ to $$$-1$$$ and from $$$1$$$ to $$$\left\lfloor\frac{c-1}{2}\right\rfloor$$$, $$$a_{c+d} = a_{c+2d}$$$;
3. each of game master's $$$m$$$ favorite number pairs $$$(x_i, y_i)$$$ appears in the sequence as consecutive values no more than once.

In any other case, game master wins. It is worth noting that game master's favorite number pairs are ordered, so if game master likes the number pair $$$(x_i, y_i)$$$, it is not guaranteed that he likes a pair $$$(y_i, x_i)$$$.

Your task is to calculate the total number of sequences of numbers from $$$1$$$ to $$$k$$$ of length $$$n$$$ that satisfy the described conditions. Calculate this number modulo $$$10^9 + 7$$$, as it may be too large.