Во время своего приключения Перси со своими друзьями, Аннабет и Гроувером, столкнулся с Эридой — богиней хаоса и раздора. Оказалось, что в современном мире у нее меньше власти, и теперь, спустя столько времени она предпочитает хаосу и раздору что-то более мирное, например, здоровое соперничество и состязания в играх.

Правда это не означает, что компании друзей будет очень просто с ней договориться, и выяснить, что она может знать про украденные молнии Зевса. В обмен на информацию они должны сыграть с ней в ее любимую игру. По правилам игры игроки по очереди бросают $$$k$$$-гранные игральные кубики и выписывают последовательность выпавших на них чисел $$$a_i$$$ (нумерация с $$$1$$$), пока последовательность не станет размера $$$n$$$ ($$$n$$$ — нечетное).

Обозначим за $$$c$$$ центральный индекс последовательности, то есть $$$\frac{n+1}{2}$$$. Ребята побеждают, только если последовательность удовлетворяет следующим трем критериям:

1. число $$$k$$$ выпало только один раз, и находится ровно в середине последовательности; более формально — $$$a_c = k$$$ и $$$a_i \ne k$$$ для всех $$$i \ne c$$$;
2. числа с одной стороны от центра на отличающихся в два раза расстояниях от него, одинаковы; то есть для любого $$$d$$$ от $$$-\left\lfloor\frac{c-1}{2}\right\rfloor$$$ до $$$-1$$$ и от $$$1$$$ до $$$\left\lfloor\frac{c-1}{2}\right\rfloor$$$ верно $$$a_{c+d} = a_{c+2d}$$$;
3. каждая из $$$m$$$ любимых пар чисел Эриды $$$(x_i, y_i)$$$ встречается в последовательности подряд не более одного раза раз.

В любом другом случае побеждает Эрида. Стоит обратить внимание, что любимые пары чисел Эриды — упорядоченные, то есть если Эриде нравится пара чисел $$$(x_i, y_i)$$$, не факт, что ей нравится $$$(y_i, x_i)$$$.

Перси заинтересовался, с какой вероятностью они смогут победить Эриду в этой игре, если каждое значение кубика выпадает равновероятно. Для этого необходимо посчитать общее количество последовательностей чисел от $$$1$$$ до $$$k$$$ длины $$$n$$$, удовлетворяющих описанным условиям. Помогите Перси посчитать это количество по модулю $$$10^9 + 7$$$, так как оно может быть слишком большим.