Цены на бензин

문제

Берляндия --- это огромная страна, состоящая из $nn$ городов. Дорожную сеть Берляндии можно представить в виде корневого дерева, то есть всего в стране $n-1n\; -\; 1$ дорога, и от любого города можно добраться до любого другого ровно по одному пути, если не посещать никакой город дважды. Для удобства представления страны, для каждого города $ii$ зафиксирован город $p_{i}p\_i$, равный первому городу, в который надо ехать из города $ii$, чтобы добраться до города $11$. Иными словами, город $p_{i}p\_i$ равен предку города $ii$, если дерево подвесить за город $11$.

В каждом городе Берляндии работает по одной заправке. У заправок особое ценообразование, и для каждой заправки зафиксирован диапазон цен, за которые там готовы продавать бензин. Заправка в городе с номером $ii$ готова продавать бензин по любой цене от $l_{i}l\_i$ до $r_{i}r\_i$ включительно.

Король Берляндии --- примерный семьянин, и в течение $mm$ лет каждый год у него рождалось по двое сыновей. Дети короля с раннего детства участвуют в государственных делах, и в конце каждого года они проверяют честность цен на бензин. С самого рождения дети короля, которые рождены в год $ii$, отвечают за проверку цен на бензин на путях от города $a_{i}a\_i$ до города $b_{i}b\_i$ и от города $c_{i}c\_i$ до города $d_{i}d\_i$ соответственно.

Проверка происходит следующим образом: оба ребенка одновременно начинают путь от городов $a_{i}a\_i$ и $c_{i}c\_i$ соответственно. Первый сын короля, рождённый в год $ii$, двигается по пути от города $a_{i}a\_i$ до города $b_{i}b\_i$, а второй --- от города $c_{i}c\_i$ до города $d_{i}d\_i$. Дети проверяют, что цена на бензин в городе $a_{i}a\_i$ совпадает с ценой на бензин в городе $c_{i}c\_i$. Далее они проверяют, что цена на бензин во втором городе на пути от $a_{i}a\_i$ до $b_{i}b\_i$ совпадает с ценой во втором городе на пути от $c_{i}c\_i$ до $d_{i}d\_i$. Далее они повторяют то же самое для пары третьих городов на их путях и так далее. В конце они проверяют, что цена на бензин в городе $b_{i}b\_i$ совпадает с ценой на бензин в городе $d_{i}d\_i$. Гарантируется, что длина пути от города $a_{i}a\_i$ до города $b_{i}b\_i$ совпадает с длиной пути от города $c_{i}c\_i$ до города $d_{i}d\_i$.

Заправки должны строго подчиняться законам, а поэтому все проверки цен на бензин не должны выявлять нарушений. Помогите заправкам Берляндии выяснить, сколькими способами они могут выставлять цены на бензин в течение $mm$ лет. Другими словами, для каждого $ii$ от $11$ до $mm$ посчитайте, сколькими способами можно выставить цены на бензин во всех заправках, чтобы после рождения первых $ii$ пар детей короля, все их проверки не выявили нарушений, а на любой заправке цена находилась в допустимом диапазоне цен. Так как число таких способов может быть большим, посчитайте ответ по модулю ${10}^9+710^9\; +\; 7$.

출력

В первой строке дано единственное целое число $nn$ ($1\le n\le 2000001\; \backslash le\; n\; \backslash le\; 200\backslash ,000$) --- число городов в Берляндии.

Во второй строке даны $(n-1)(n\; -\; 1)$ чисел $p_2,p_3,p_4,\dots ,p_{n}p\_2,\backslash \; p\_3,\backslash \; p\_4,\backslash \; \backslash ldots,\backslash \; p\_n$ ($1\le p_i\le n1\; \backslash le\; p\_i\; \backslash le\; n$), где $p_{i}p\_i$ обозначает номер следующего города на пути из города $ii$ в город $11$.

В каждой из следующих строк даны по два целых числа $l_{i}l\_i$ и $r_{i}r\_i$ (), задающие допустимый диапазон цен на заправке номер $ii$.

В следующей строке дано единственное целое число $mm$ ($1\le m\le 2000001\; \backslash le\; m\; \backslash le\; 200\backslash ,000$) --- количество лет, в течение которых у короля рождалось по два сына.

В каждой из следующих $mm$ строк даны по четыре целых числа $a_{i}a\_i$, $b_{i}b\_i$, $c_{i}c\_i$ и $d_{i}d\_i$ ($1\le a_i,b_i,c_i,d_i\le n1\; \backslash le\; a\_i,\; b\_i,\; c\_i,\; d\_i\; \backslash le\; n$), задающие два пути, на которых будут проверять цены на бензин дети короля, рождённые в год $ii$. Гарантируется, что длина пути между городами $a_{i}a\_i$ и $b_{i}b\_i$ равна длине пути между городами $c_{i}c\_i$ и $d_{i}d\_i$.

힌트

Рассмотрим первый пример.

После рождения первых двух сыновей цены в городах $11$ и $22$ должны быть равны. Всего существует 2 способа выбрать одинаковую цену на бензин для городов $11$ и $22$, чтобы она входила в допустимый диапазон цен для этих городов. Значит, всего способов выставить цены на бензин: $2\cdot 3\cdot 3\cdot 1=182\; \backslash cdot\; 3\; \backslash cdot\; 3\; \backslash cdot\; 1\; =\; 18$.

Вторая пара сыновей будет проверять цены на путях $1-21\; -\; 2$ и $2-12\; -\; 1$. Значит, цены на бензин в городах $11$ и $22$ должны совпадать, что уже выполняется. Поэтому после рождения второй пары сыновей ответ никак не изменился.

Третья пара сыновей будет проверять цены на путях $3-1-2-43\; -\; 1\; -\; 2\; -\; 4$ и $4-2-1-34\; -\; 2\; -\; 1\; -\; 3$. Тогда цена не бензин в городе $33$ должна быть равна цене в городе $44$, и цена в городе $11$ должна быть равна цене в городе $22$. Цены в городах $11$ и $22$ уже одинаковые. Для городов $33$ и $44$ существует 2 способа выбрать одинаковую цену на бензин, чтобы она входила в допустимый диапазон цен для этих городов. Значит, всего способов выставить цены на бензин: $2\cdot 2\cdot 1=62\; \backslash cdot\; 2\; \backslash cdot\; 1\; =\; 6$.

Четвертая пара сыновей будет проверять цены на путях $3-1-2-43\; -\; 1\; -\; 2\; -\; 4$ и $3-1-2-53\; -\; 1\; -\; 2\; -\; 5$. Это означает, что цены в городах $44$ и $55$ должны быть равны, и так как цены в городах $33$ и $44$ уже совпадают, то в городах $33$, $44$ и $55$ должна быть одинаковая цена на бензин. Цена на бензин в городе $33$ должна быть не больше 3, а цена на бензин в городе $55$ должна быть не меньше 4. Значит, после рождения четвёртой пары сыновей не существует способов выставить цены на бензин так, чтобы все проверки выполнялись и цены находились в необходимых диапазонах.