Олег очень любит двоичные последовательности - последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из \(n\) элементов. Для выписанной последовательности Олег посчитал Z-функцию.
Z-функцией последовательности \(s_1, \ldots, s_n\) называется массив \(z[1..n]\), в котором:
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.
Найдите число искомых последовательностей и выведите его по модулю \(10^9 + 7\). Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
В первой строке входного файла находится целое число \(n\) - длина исходной двоичной последовательности (\(1 \le n \le 1000\)). Во второй строке входного файла находятся \(n\) целых чисел \(z[1], \ldots, z[n]\), где \(z[i]\) - значение Z-функции в позиции \(i\), или \(-1\), если значение в \(i\)-й позиции было закрашено (\(-1 \le z[i] \le n\)).
В выходной файл выведите единственное число - остаток от деления числа подходящих двоичных последовательностей на число \(10^9 + 7\).
В первом примере подходят последовательности \(\langle 0, 1, 0 \rangle\) и \(\langle 1, 0, 1 \rangle\).
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере \(z[2] = 3\), что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.
3 0 0 1
2
4 0 0 1 0
0
3 0 3 -1
0
3 -1 -1 -1
8
В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено \(n\) забавных памятников.
Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более \(r\) метров.
Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.
В первой строке входного файла находятся два целых числа \(n\) и \(r\) (\(2 \le n \le 300\,000\), \(1 \le r \le 10^9\)) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.
Во второй строке задано \(n\) положительных чисел \(d_1, \ldots, d_n\), где \(d_i\) - расстояние от \(i\)-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (\(1 \le d_1 < d_2 < \ldots < d_n \le 10^9\)).
Выведите одно число - число способов выбрать два памятника для организации свиданий.
В приведенном примере Маша может выбрать памятники под номерами 1 и 4 или памятники 2 и 4.
4 4 1 3 5 8
2
Гномы продолжают искать золото предков в недрах Одинокой горы. Недра Одинокой горы представляют собой \(n\) пещер, некоторые из которых соединены двусторонними переходами. При этом из каждой пещеры в любую другую можно попасть по переходам, причем это можно сделать единственным способом.
Гномы разделились на два отряда, которые начали свои поиски с пещер \(u_0\) и \(v_0\), соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.
Чтобы как можно лучше обследовать недра Одинокой горы, гномы хотят, чтобы поиски продолжались как можно дольше. По заданной карте пещер в Одинокой горе и начальному положению отрядов гномов определите, какое максимальное время могут продолжаться поиски сокровищ.
В первой строке число \(n\) (\(2 \le n \le 200\,000\)) - число пещер в Одинокой горе.
В следующих \(n - 1\) строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер \(v\) и \(u\), соединенных переходом
(\(1 \le v, u \le n\)).
В следующей строке заданы номера пещер \(v_0\) и \(u_0\), в которых исходно находятся два отряда гномов (\(1 \le v_0, u_0 \le n\), \(v_0 \ne u_0\)).
Выведите максимальное число минут, которое могут продолжаться поиски сокровищ.
6 1 2 2 3 3 4 4 5 5 6 4 5
2
8 1 2 2 3 3 4 2 5 5 6 3 7 7 8 1 8
4
Том Сойер уговорил \(n\) своих друзей помочь ему в нелегком деле покраски забора, окружающего дом тетушки Полли. Забор представляет собой \(k\) последовательных досок, пронумерованных от 1 до \(k\), причем после \(k\)-й доски опять идет первая.
Друзья Тома очень привередливы, \(i\)-й друг согласен участвовать в покраске только в том случае, если ему дадут покрасить участок из ровно \(a_i\) последовательных досок.
Кисточка у Тома только одна, поэтому друзья будут красить по очереди и сразу весь отведенный им отрезок. Тому остается лишь выбрать порядок, в котором приглашать друзей, а также выбрать для каждого желаемое количество последовательных досок.
При этом каждый из друзей Тома готов красить как еще неокрашенную доску забора, так и доску, которую уже покрасил один из его предшественников. Тем не менее, друзья получают больше удовольствия от покраски неокрашенной доски. Том хочет выбрать число \(x\) и распределить отрезки забора для покраски таким образом, чтобы каждый из его друзей покрасил хотя бы \(x\) неокрашенных досок. Том очень любит своих друзей и хочет, чтобы каждый из них получил от процесса покраски забора максимальное удовольствие, поэтому он пытается максимизировать \(x\).
Помогите Тому понять, сколько радости он сможет доставить своим друзьям.
Первая строка входного файла содержит два целых числа \(n\) (\(1 \le n \le 10^5\)) и \(k\) (\(1 \le k \le 10^9\)). Следующая строка содержит \(n\) целых чисел - значения \(a_i\) (\(1 \le a_i \le k\)).
Выведите одно число - максимальное возможное значение \(x\).
В первом примере \(x = 5\), так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.
Во втором примере достичь \(x = 2\) можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).
2 100 5 10
5
4 10 7 8 3 5
2
Неотъемлемой частью программного обеспечения любого мобильного телефона является записная книжка. В самых первых мобильных телефонах в ней можно было хранить лишь имена абонентов и их телефонные номера. В более современных моделях в ней можно также хранить множество другой полезной информации - электронный адрес человека, его фотографию, ссылки на его страницы в социальных сетях и дату его рождения. Однако, при реализации даже самой простой версии этой программы, позволяющей работать только с телефонными номерами, разработчики иногда сталкиваются с некоторыми сложностями.
Будем считать, что любой телефонный номер состоит из 11 цифр и делится на три части, каждая из которых является числом без ведущих нулей. Первая часть состоит из одной, двух или трех цифр и является кодом страны, в которой этот телефон зарегистрирован. Вторая часть может состоять из трех, четырех или пяти цифр, и может являться или кодом региона, в котором зарегистрирован номер, или кодом мобильного оператора, которому этот номер принадлежит. Третья часть состоит из всех оставшихся цифр номера и является номером конкретного абонента.
При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ <<+>>, код региона или оператора берется в скобки, номер абонента разделяется символами <<->> на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:
Естественно, что человек, заносящий новый номер в записную книжку своего телефона, не станет задумываться об этих правилах, а просто введет его как последовательность из 11 цифр. Однако, перед отображением номера на экране, программное обеспечение телефона должно выяснить, какая часть этого номера является кодом страны, какая - кодом региона или оператора, а какая - номером абонента, и отформатировать номер по правилам, описанным выше. Чтобы сделать эту задачу разрешимой, в память телефона записывается информация о том, какие в данный момент существуют коды государств и какие в этих государствах существуют коды операторов или регионов. Вам необходимо реализовать программу, которая, имея эту информацию, будет правильно форматировать номера, сохраненные в записной книжке телефона.
Первая строка файла содержит одно целое число \(n\) (\(1 \le n \le 100\)) - количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют \(n\) описаний этих государств, разделенных переводами строк.
Первая строка описания каждого государства содержит два целых числа \(c\) и \(k\) (\(1 \le c \le 999\), \(1 \le k \le 100\)) - телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие \(k\) строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 - коды операторов или регионов, зарегистрированных в этом государстве.
Следующая строка входного файла содержит одно целое число \(m\) (\(1 \le m \le 10{\,}000\)) - количество телефонных номеров, которые необходимо отформатировать. Следующие \(m\) строк содержат сами номера - строки, состоящие ровно из 11 цифр.
Гарантируется, что ни один данный вам номер невозможно разбить на код государства, код оператора или региона и номер абонента более, чем одним способом.
Выведите номера, данные вам во входном файле, отформатированными по правилам, описанным в условии. Каждый номер необходимо вывести в отдельной строке. Номера необходимо выводить в том же порядке, в котором они были перечислены во входном файле.
Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово "Incorrect".
2 7 3 981 3517 812 351 3 34712 1234 963 8 79818266456 35196328463 78122472557 01234567890 73517960326 35134712239 35112342013 78120102030
+7(981)826-64-56 +351(963)284-63 +7(812)247-25-57 Incorrect +7(3517)96-03-26 +351(34712)239 +351(1234)20-13 Incorrect