Отель «Континенталь», в котором случается достаточно много ключевых событий в жизни Джона Уика, имеет долгую историю. И построен он был, несмотря на все ресурсы Правления Кланов и Старейшины, не в один день.

Всего отдель был построен за $$$n$$$ дней. В первый день было построено основание «Континенталя» в виде прямоугольника размером $$$a_1 \times b_1$$$. Затем в $$$i$$$-й день к текущему основанию с краю достраивался еще один блок размером $$$a_i \times b_i$$$ так, чтобы основание оставалось прямоугольником.

Иными словами, текущее основание и прямоугольник размером $$$a_i \times b_i$$$ присоединялись друг к другу одинаковой стороной. Прямоугольник мог быть повернут на $$$90^\circ$$$ и присоединен к любой из сторон текущего основания, если сам имел равную ей сторону.

Джон, чтобы незаметно пробраться в «Континенталь» к Винстону, добыл записи о всех $$$n$$$ днях постройки. Теперь он хочет понять, правдивы ли эти записи, и, если да, какими могут быть размеры текущего «Континенталя».

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

Джон Уик оказался втянут в противостояние между старым Правлением и новой фракцией. Исход противостояния определится тем, к какой фракции примкнет сам Джон, но он пока предпочитает сохранять нейтралитет, поэтому ему стоит тщательно планировать свои перемещения.

Карта городов, между которыми Джону может понадобиться перемещаться, представляет собой неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребер. Граф не обязательно связный, то есть не обязательно между каждой парой городов есть путь. В каждом городе большее влияние имеет ровно одна из двух фракций.

Джон считает распределение влияния фракций по городам достаточно нейтральным, если в любых двух городах, соединенных ребром, главенствуют разные фракции. Он может подтянуть старые связи и использовать свои Маркеры, чтобы изменить баланс сил в некоторых городах, однако он считает неблагоразумным вмешиваться больше, чем требуется. Всего есть $$$k$$$ городов, на которые Джон может оказать влияние: $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$.

Помогите Джону определить, в каком минимальном количестве городов ему следует поменять влияние одной фракции на другой, чтобы распределение фракций стало нейтральным.

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

После того, как Джон Уик был объявлен экскомьюникадо, у него оставался всего лишь час, прежде чем за его голову официально будет выставлена награда. За этот час ему было необходимо собрать все, что может помочь ему выжить.

В Нью-Йоркской библиотеке в одной из книг Джон хранит Маркер и еще несколько предметов, которые могут помочь ему выбраться из ситуации. Чтобы найти эту книгу, Джону необходимо вспомнить ее библиотечный номер — строку из маленьких латинских букв длины $$$n$$$.

У Джона записана подсказка $$$s$$$, которая может помочь ему вспомнить номер. Он помнит, что номер можно получить из $$$s$$$ следующим алгоритмом:

1. выбрать в $$$s$$$ некоторый символ $$$s_i$$$, после чего выписать его на бумагу;
2. разделить $$$s$$$ по этому символу на две части: $$$s_l = \overline{s_1 s_2 \ldots s_{i - 1}}$$$ и $$$s_r = \overline{s_{i + 1} s_{i + 2} \ldots s_n}$$$;
3. применить последовательно этот же алгоритм сначала к $$$s_l$$$, а потом к $$$s_r$$$.

Известно, что библиотечный номер книги — это лексикографически минимальная из строк, которые можно получить из $$$s$$$ описанным образом. Помогите Джону его восстановить.

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

За голову Джона Уика опять назначена награда, и лидеры одного очень влиятельного клана решили во что бы то ни стало ее получить. В клане есть $$$n$$$ оперативников, которые могут принять участие в охоте за целью. Поскольку всем известно, что Джон — опасная цель, из множества оперативников было решено выбрать несколько групп размерами от $$$3$$$ до $$$k$$$ включительно.

Все $$$n$$$ человек имеют в клане строгую иерархию в виде подвешенного дерева: самый опытный оперативник имеет номер $$$1$$$, у каждого из остальных есть один непосредственный начальник $$$p_i \lt i$$$. У оперативников есть четкие правила, по которым они формируют группы. А именно, каждый оперативник готов быть в команде либо со своим непосредственным начальником, либо с несколькими своими непосредственными подчиненными, и больше ни с кем. Таким образом, любая команда будет состоять из какого-то оперативника с хотя бы двумя его непосредственными подчиненными.

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

Поскольку ответ на задачу может быть слишком большим, выведите его по модулю $$$10^9 + 7$$$.

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

Здесь за $$$\mathrm{deg}(v)$$$ обозначено количество непосредственных подчиненных оперативника номер $$$v$$$.