Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:

1. A и B - различные планеты.

2. В действующей сети межпланетных магистралей существует путь между A и B .

3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.

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

На лесистой луне Эндора находится, если верить Имперской Книге Рекордов, самая длинная ветка в галактике. На этой ветке длиной L метров сидит N дружелюбных хамелеонов. Каждый хамелеон ходит вдоль ветки со скоростью 1 м/с в одном из двух возможных направлений (налево или направо), а также имеет собственный цвет среди одного из K возможных.

Известно, что хамелеоны на Эндоры следуют древним законам, в соответствии с которыми любая прогулка вдоль ветки должна продолжаться до ее конца (после чего хамелеон спрыгивает с ветки), а в случае столкновения двух хамелеонов, они должны развернуться на 180 градусов и продолжить движение в противоположном направлении. Кроме того, при таком столкновении, если хамелеон, двигавшийся налево, имел цвет a , а хамелеон, двигавшийся направо - цвет b , то после разворота первый хамелеон изменит свой цвет на b , а второй хамелеон - на ( a + b ) modK .

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

Перика начала играть на пианино. Оно у нее особенное - на нем есть N клавиш, и на каждой написано число a _i . В процессе игры Перика одновременно нажимает K клавиш, но так как пианино особенное, звук издаст только клавиша с наибольшим числом среди нажатых. Перика собирается нажать каждую из возможных комбинаций из K клавиш и хочет знать сумму чисел на тех клавишах, которые при этом издадут звуки.

Помогите Перике и ответьте на ее вопрос. Так как ответ может быть очень большим, выведите его по модулю 1 000 000 007.

Вам дан массив целых чисел длины N . Пусть s ₁ , s ₂ , ... , s _q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 ^N - 1 .

Массив A лексикографически меньше массива B , если A _i < B _i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v ₁ , v ₂ , ... , v _p , как: h ( s )  =  ( v ₁ · B ^{p - 1} + v ₂ · B ^{p - 2} + ... + v _{p - 1} · B + v _p ) mod M , где B и M - данные числа.

Посчитайте h ( s ₁ ) , h ( s ₂ ) , ... , h ( s _K ) для данного K .

Мирко и Славко играют в игру. Мирко ходит первым и выбирает непустое множество пар чисел от 1 до N (включительно). При этом числа в одной паре должны быть различны и взаимнопросты. Например, для N = 5 , Мирко может выбрать такое множество пар: {(1, 2), (3, 4), (2, 5), (3, 5)}.

Славко ходит вторым и его задача - найти разделяющий элемент для множества пар Мирко. Разделяющим элементом для множества пар называется такое число x из диапазона [2: N ] , что для каждой пары ( a , b ) из множества выполняется одно из двух условий:

1. a , b < x

2. a , b ≥ x

Например, множество пар {(1, 2), (3, 4)} имеет разделяющий элемент x = 3 .

Если разделяющий элемент существует, Славко обязательно его найдет, и тогда он выиграет. Мирко же выиграет, если Славко не сможет найти разделяющий элемент. Он просит вас помочь: определите, как много множеств пар, удовлетворяющих условию, он может выбрать, чтобы гарантированно выиграть. Так как это число может быть очень большим, выведите его по модулю 1 000 000 000.