Задача A. Укладка плитки ≡

Условие

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

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

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹ + 7.

Пояснения к примерам

Внимание! Третий тест не подходит под ограничения для первых трех подзадач, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на все тесты из примера. Решение должно выводить правильный ответ на третий тест даже, если оно рассчитано на решение только каких-либо подзадач из первых трех.

Рисунок 1. Все способы укладки плиток в первом примере

Рисунок 2. Все способы укладки плиток в третьем примере. Уже уложенная плитка отмечена серым цветом.

Система оценивания и описание подзадач

Подзадача 1 (20 баллов)

1 ≤ n ≤ 8, k = 0

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

Подзадача 2 (20 баллов)

1 ≤ n ≤ 1000, k = 0

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

Подзадача 3 (20 баллов)

1 ≤ n ≤ 100 000, k = 0

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

Подзадача 4 (40 баллов)

1 ≤ n ≤ 100 000, 1 ≤ k ≤ 2 n

В этой подзадаче 20 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток.

Последующие k строк содержат по два целых числа x_i и y_i, которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на x_i-м метре коридора в y_i-м ряду.

Формат выходного файла

Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹ + 7.

Ограничения

1 ≤ n ≤ 100 000; 0 ≤ k ≤ 2 n; 1 ≤ x_i ≤ n; 1 ≤ y_i ≤ 2.

Примеры тестов

2 0

7

3 0

22

3 1
2 1

8

Задача B. Сплошные числа ≡

Условие

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа могла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

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

Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.

Примечание

Формат входного файла

Первая строка входного файла содержит три целых числа — n C k. Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

Формат выходного файла

Выходной файл должен содержать последние k цифр искомого количества последовательностей без ведущих нулей.

Ограничения

1 ≤ n ≤ 50000

1 ≤ C ≤ 10⁸

1 ≤ k ≤ 18

Примеры тестов

3 11 2
111

3

19 9 1
0123456789876543210

1

1 8 3
9

0

Задача C. Интересные числа ≡

Условие

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 — интересные.

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 10⁹ + 7.

Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 10⁹ + 7.

Формат входного файла

Входной файл содержит две строки. Первая строка содержит число L, вторая строка содержит число R.

Формат выходного файла

Выходной файл должен одно целое число — остаток от деления количества интересных чисел, лежащих в диапазоне от L до R включительно, на 10⁹ + 7.

Ограничения

1 ≤ L ≤ R ≤ 10¹⁰⁰

Описание подзадач и системы оценивания

Подзадача 1 (21 балл)

L = 1, R ≤ 1000.

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

Подзадача 2 (22 балла)

1 ≤ L ≤ R ≤ 10¹⁸.

В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (24 балла)

L = 1, R = 10^k для некоторого целого k, 2 ≤ k ≤ 100.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (33 балла)

1 ≤ L ≤ R ≤ 10¹⁰⁰.

В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

1
100

54

Задача D. Простые пути в дереве ≡

Условие

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

Формат входного файла

На первой строке целое число n. Следующие n−1 строка содержат пары чисел от 1 до n  — ребра графа.

Формат выходного файла

n−1 строка. i-я строка должна содержать целое число  — ответ для i-го ребра.

Ограничения

2 ≤ n ≤ 300000

Примеры тестов

5
1 2
2 3
2 4
5 1

13
8
8
9

Задача E. Выбор вершин взвешенного дерева ≡

Условие

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

Рассмотрим все допустимые множества вершин графа. Для каждого такого множества вычислим сумму чисел, написанных в его вершинах. Какова максимальная из этих сумм?

Формат входного файла

Граф в этой задаче задан в виде корневого дерева. В графе выделена вершина — корень дерева. Для каждой вершины i, не являющейся корнем, задан номер вершины-предка p_i в корневом дереве. Дерево, заданное таким образом, состоит из рёбер i — p_i для всех вершин i, кроме корня.

В первой строке входного файла записано целое число n  — количество вершин в графе . В следующих n строках задан граф. В i-й из этих строк записаны через пробел два целых числа p_i и q_i; здесь p_i  — номер вершины-предка i-ой вершины, а q_i  — число, записанное в этой вершине. Для корня дерева p_i = 0; для всех остальных вершин 1 ≤ p_i ≤ n.

Гарантируется, что заданный во входном файле граф является деревом.

Формат выходного файла

В первой строке выходного файла выведите одно число — максимальную сумму чисел в допустимом множестве.

Ограничения

1 ≤ n ≤ 100

1 ≤ p_i ≤ n

|q_i| ≤ 10⁴

Примеры тестов

5
0 1
1 2
1 3
2 4
3 5

10

6
5 8
6 0
5 -1
1 1
0 3
1 2

8

Задача F. Красота фейерверка ≡

Условие

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

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

На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин 2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.

Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T¹ — само дерево T. Для m > 1 рассмотрим дерево T^m − 1. Выполним следующую операцию: для каждого листа x дерева T^m − 1 создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом T^m.

На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.

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

Для того, чтобы оценить красоту фейерверка, необходимо определить, какое максимальное количество вершин может содержать путь в дереве, которым представляется фейерверк. На рис. 3 приведен путь в дереве T², содержащий максимальное количество вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.

Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

Формат входных данных

Первая строка входных данных содержит два натуральных числа n и m — количество вершин в базовом дереве фейерверка T и его мощность.

Вторая строка описывает дерево T и содержит (n − 1) целых чисел: p₂, p₃, ..., p_n — номера родителей вершин 2, 3, ..., n, соответственно.

Формат выходных данных

Требуется вывести одно целое число — красоту фейерверка, представляемого деревом T^m.

Ограничения

3 ≤ n ≤ 200000, 1 ≤ m ≤ 200000

1 ≤ p_i ≤ i − 1

Описание подзадач и системы оценивания

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

Примеры тестов

4 2
1 1 2

10