Алгоритмы

Разложение на простые множители числа 12 можно записать тремя способами:

  12=2·2·3=2·3·2=3·2·2

А сколькими способами можно записать разложение на простые множители числа N?

Входные данные
Вводится одно натуральное число N (2 <= N <= 1 000 ).

Выходные данные
Выведите одно число – количество различных записей разложения.

Примеры

№	Входные данные	Выходные данные
1	12	3
2	13	1

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

По информации о будильниках и текущему времени и дню недели определите, когда прозвонит очередной будильник.

Входные данные
В первой строке вводятся три числа, задающие текущее время: день недели (от 1 до 7), часы и минуты.

Во второй строке вводится одно натуральное число N, не превосходящее 100 – количество будильников.

В следующих N строках вводятся описания N будильников. Описание каждого будильника состоит из трех чисел: дня недели (число от 1 до 7 для понедельника,  …, воскресенья, соответственно, 0 – если будильник должен звонить каждый день), часов (от 0 до 23), минут (от 0 до 59).


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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 10 20 2 1 23 15 0 10 10	3 10 10
2	7 1 1 3 7 0 59 7 23 59 7 1 1	7 1 1	Во втором примере третий будильник будет звенеть в начальный момент времени.

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

Входные данные
Вводится сначала стоимость билета, который хочет приобрести пассажир, затем общее количество купюр и монет, которые он опустил в автомат, а затем достоинства каждой из этих купюр и монет. Входные данные записаны в одной строке и разделены пробелами. Известно, что сумма всех купюр больше, чем стоимость билета. Во всех тестовых примерах стоимость билета – натуральное число, не превосходящее 1 000 рублей, количество купюр и монет не более 50, достоинство каждой не превосходит 500 рублей. Общая сумма денег, опущенных в автомат покупателем, превосходит стоимость билета.

Выходные данные
Программа должна вычислить, какими купюрами и монетами можно выдать сдачу, и вывести достоинство каждой из этих купюр или монет в произвольном порядке. Автомат может выдавать сдачу купюрами в 10, 50, 100 и 500 рублей, а также монетами в 1, 2 и 5 рублей. Если решений несколько, требуется выдать одно любое из них. Если решений нет, требуется выдать текст:

Sorry! Our monetary system is not perfect!
Please, choose another way to pay!
Thank you!

Примеры

№	Входные данные	Выходные данные
1	100 1 500	50 100 100 100 50

У меня в прихожей стоят в ряд 20 тапочек – 10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше. Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.

Входные данные
Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.
Выходные данные
Программа должна вывести количество тапочек между самыми удобными тапочками, или -1, если таких нет.
 

Примеры

№	Входные данные	Выходные данные
1	1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0	0

На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

Входные данные
Сначала вводится одно целое число N (0 < N ≤ 1000).

В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), оставшиеся два — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч. 30 мин. до 18 ч. 30 мин., ежесуточно работает 480 минут.

Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.

Выходные данные
Требуется вывести одно число — суммарное время за сутки (в минутах), на протяжении которого работают все N касс.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 0 23 0 12 0 12 0 22 0 2 0	120	Первая касса работает с часу до 23 часов, вторая – круглосуточно, третья – с 22 часов до 2 часов ночи следующего дня. Таким образом, все три кассы одновременно работают с 22 до 23 часов и с часу до двух часов, то есть 120 минут.
2	2 9 30 14 0 14 15 21 0	0	Первая касса работает до 14 часов, а вторая начинает работать в 14 часов 15 минут, то есть одновременно кассы не работают.
3	2 14 00 18 00 10 00 14 01	1	Вместе кассы работают лишь одну минуту – с 14:00 до 14:01 (в 14:01 вторая касса уже не работает).

Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.

Входные данные
Сначала вводится число N (1 ≤ N ≤ 64) – количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 1 1 2 2 1	8	Вырезан уголок из трех клеток. Сумма длин его сторон равна 8.
2	1 8 8	4	Вырезана одна клетка. Ее периметр равен 4.

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

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

Входные данные
Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии (2≤P_i≤50) и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Выходные данные
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).
 

Примеры

№	Входные данные	Выходные данные
1	5 2 4 1 2 3 4 2 5 3 3 1	0
2	5 5 2 1 2 2 1 3 2 2 3 2 3 4 2 4 5 1 5	2
3	10 2 6 1 3 5 7 4 9 6 2 4 6 8 10 7 3 8	1
4	4 2 2 1 2 2 3 4 1 3	-1

X мальчиков и Y девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду. Напишите программу, которая выдаст, как нужно сесть мальчикам и девочкам, чтобы рядом с каждым мальчиком сидела хотя бы одна девочка, а рядом с каждой девочкой — хотя бы один мальчик.

Входные данные
Вводятся два числа — X и Y (оба числа натуральные, не превосходящие 100).

Выходные данные
Выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры

№	Входные данные	Выходные данные
1	5 5	BGBGBGBGBG
2	5 3	BGBGBBGB
3	100 1	NO SOLUTION

У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 5 4 1 2 2 3 1 4 3 5	3	G′ может быть равен G′ или одному из двух следующих графов: 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5
2	7 4 6 1 2 2 3 3 4 1 3 2 4 1 4 5 5 1 2 2 3 3 4 4 5 1 5 5 7 1 2 1 3 1 5 2 4 3 3 3 4 4 5 6 6 1 2 2 3 3 4 4 5 5 6 6 6 6 7 1 2 2 3 1 3 1 4 4 5 5 6 1 6 10 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 22 28 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 8 3 9 8 10 10 11 10 12 10 13 10 14 11 15 12 16 13 17 14 18 9 15 9 16 9 17 9 18 15 19 19 20 15 20 16 21 21 22 16 22	45 35 11 1 15 371842544 256838540	Это пример более крупного теста. Обязательно выводите ответ по модулю \(10^9+7\). Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).

 

Маша и Даша играют в игру с N (\(1<=N<=10^5\)) кучками камушков, где i-ая кучка содержит ai камешков (\(1<=i<=N\), \(1<=a_i<=10^6\)). Они ходят по очереди, первой ходит Маша.

• Сначала Маша выбирает некоторое положительное число s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков.
• Затем Даша выбирает некоторое положительное число s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
• Затем Маша выбирает некоторое положительное число s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков.
• В общем случае si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.

Проигрывает тот, кто не может сделать ход.

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

Входные данные
Первая строка содержит N.
Вторая строка содержит N разделённых одиночными пробелами целых чисел a1,…,aN.


Выходные данные
Выведите количество способов, которыми Маша может удалить камушки на первом ходу, чтобы гарантировать себе выигрыш.
Для вычислений используйте 64-ное целое например, "long long" в C/C++.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 7	4	Маша выбирает 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.
2	6 3 2 3 2 3 1	8	Маша выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Маша сделает последний ход.

Наскучившись стандартными двумерными произведениями искусства (а также разочаровавшись тем, что другие копируют ее работы), великая художница Пикоусо решила перейти к более минималистичному, одномерному стилю. Ее последняя картина может быть описана одномерным массивом цветов длины N (\(1<=N<=300\)), где каждый цвет указывается целым числом в интервале \(1…N\).
К великому разочарованию Пикоусо, ее конкурент Муне, похоже, придумал, как копировать даже эти одномерные картины! Муне закрашивает один интервал одним цветом, ждет, пока он высохнет, затем красит другой интервал и так далее. Муне может использовать каждый из N цветов столько раз, сколько пожелает (возможно ни одного).

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


Входные данные
Первая строка содержит число N. Следующая строка содержит N целых чисел в интервале \(1…N\), указывающих цвет каждой ячейки в картине Пикоусо.

 

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

Примеры

№	Входные данные	Выходные данные
1	10 1 2 3 4 1 4 3 2 1 6	6

 

Пояснение

В этом примере Муне может скопироват картину так: (незакрашенные ячейки обозначены цветом 0).

Изначально весь массив не закрашен:
0 0 0 0 0 0 0 0 0 0
Муне закрашивает первые 9 ячеек цветом 1:
1 1 1 1 1 1 1 1 1 0
Муне закрашивает интервал цветом 2:
1 2 2 2 2 2 2 2 1 0
Муне закрашивает интервал цветом 3:
1 2 3 3 3 3 3 2 1 0
Муне закрашивает интервал цветом 4:
1 2 3 4 4 4 3 2 1 0
Муне закрашивает одну ячейку цветом 1:
1 2 3 4 1 4 3 2 1 0
Муне закрашивает последнюю ячейку цветом 6:
1 2 3 4 1 4 3 2 1 6
Заметим, что на первом движении кисти можно было закрасить цветом 1 и десятую ячейку. Это не изменило бы финальное состояние.

Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски).  Размещение коров весьма занимательно. Для каждой ячейки (x,y) с \(x>=0\) и \(y>=0\), существует корова в ячейке (x,y), если для всех целых чисел \(k>=0\), остатки \(\lfloor {\frac {x}{3^k} }\rfloor\) и \(\lfloor {\frac {y}{3^k} }\rfloor\) по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для \(0<=x,y<9\), которые содержат коров обозначены цифрой 1 на рисунке ниже.

 x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

Ферме Джон интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт Q вопросов, кажый содержит три целых числа xi,yi,di. Для каждого вопроса Фермер Джон хочет знать, сколько коров в ячейках с (xi, yi) до (xi+di, yi+di) (включая конечные точки).


Входные данные
Первая строка содержит Q (\(1<=Q<=10^4\)) - количество вопросов.
Каждая из следующих Q строк содержит 3 целых числа di, xi, и yi (\(0<=x_i,y_i,d_i<=10^{18}\)).


Выходные данные
Q строк, по одной для каждого вопроса - одно целое число - ответ.
 
 

Примеры

№	Входные данные	Выходные данные
1	8 10 0 0 10 0 1 9 0 2 8 0 2 0 1 7 1 1 7 2 1 7 1000000000000000000 1000000000000000000 1000000000000000000	11 0 4 3 1 2 2 1000000000000000001

Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.

Корова Беси хочет посетить N своих предшественников, которые жили много раньше (\(1<=N<=0x10000\)). 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной.

К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более K прыжков во времени (\(1<=K<=N\)). Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более K прыжков во времени по пути.

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

Входные данные
Первая строка ввода содержит N и K. Следующие N строк содержат N различных целых чисел в интервале \(1…10^9\), указывающих сколько лет назад жил каждый из предшественников Беси.

Выходные данные
Выведите минимальное количество лет, которое потребуется Беси, чтобы посетить всех своих предшественников и вернуться в настоящий год.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 3 101 85 100 46 95	36	Один из способов для Беси посетить всех своих предшественников за 36 лет таков: Войти в портал в текущем году и вернуться на 48 лет в прошлое. Подождать 12 лет затем войтив портал в 36 лет в прошлом и пропутешествовать 108 лет в прошлое. Подождать 24 года, затем зайти в портал в 84 года в прошлом и пропутешествовать обратно в текущий год.

Известно, что в Китайском календаре года следуют 12-летнему циклу: Ox(Бык), Tiger(Тигр), Rabbit(Кролик), Dragon(Дракон), Snake(Змея), Horse(Лошадь), Goat(Коза), Monkey(Обезьяна), Rooster(Петух), Dog(Собака), Pig(Свинья), Rat(Крыса), и затем Ox опять. 
Уже много лет корова Беси гордится, что она родилась в год Быка. Её подружка Эльза хочет узнать сколько лет отделяет её рождение от рождения Беси и надеется, что вы поможете ей узнать это, основываясь на отношениях между датами рождения некоторых коров на ферме.

Входные данные
Первая строка ввода содержит целое число N (\(1<=N<=100\)). Каждая из следующих N строк содержит 8-словную фразу указывающую отношение между датами рождения двух коров. В следующей форме

"Mildred born in previous Dragon year from Bessie",

или

"Mildred born in next Dragon year from Bessie" (previous - предыдуший, next-следующий).

Последнее слово - имя коровы, которое или Bessie или корова ранее упомянутая в предыдущей строке ввода.
Первое слово - имя коровы, которая не Bessie и ещё не упоминалась на вводе. Все имена коров имеют не более 10 символов a..z или A..Z.

5-ое слово - один из знаков зодиака, указаных ранее.

4-ое слово либо "previous" либо "next". Например, фраза "Mildred born in previous Dragon year from Bessie", означает, что год рождения Mildred был год Дракона(Dragon), ближайший и строго раньше (не равен) года рождения Беси.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	4 Mildred born in previous Dragon year from Bessie Gretta born in previous Monkey year from Mildred Elsie born in next Ox year from Gretta Paulina born in next Dog year from Bessie	12	В примере выше Elsie родилась на 12 лет раньше Bessie. Mildred родилась на 9 лет раньше Bessie. Gretta родилась на 17 лет раньше Bessie. Paulina родилась на 9 лет раньше Bessie.

Фермер Джон решил заменить изгородь вокруг своего пастбища.
Эта новая изгородь описывается строкой символов, каждый из которых "N" (north), "E" (east), "S" (south), или "W" (west). Каждый символ описывает 1 метр изгороди. Например, если строка NESW, это означает, что изгородь начинатся одним метром на север, затем 1 метр на восток, затем 1 метр на юг, и затем 1 метр на запад, возвращаясь в стратовую точку.

Изгородь всегда заканчивается в той же позиции, где стартовала, и это - единственная точка, посещенная более одного раза путем изгороди (а стартовая точка, единственная точка посещённая второй раз - в конце пути). Как следствие, изгородь огораживает один связный регион травяного пастбища, даже если этот регион может иметь довольно странную форму.

Фермер Джон хочет узнать, указанный путь обходится по часовой стреле или против часовой стрелки? По часовой стрелке - огороженный регион находится по правую сторону от изгороди, если идти по пути, определённому строкой. Против часовой стрелки - огороженный регион находится по левую сторону от изгороди, если идти по пути, определённому строкой.

Входные данные: 
Первая строка содержит целое число N (1≤N≤20). Каждая из последующих N строк содержит строку длиной не менее 4 символов и не более 100, описывающую путь изгороди.
Выходные данные: 
Для каждого из N путей, описанных по вводе, выведите строку содержащую "CW" (clockwise - по часовой стрелке) или "CCW" (counterclockwise - против часовой стрелки).
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 NESW WSSSEENWNEESSENNNNWWWS	CW CCW	Оба пути   (? символ "пробел") обозначает стартовую точку: *>* ^ v <*   *<*<*<*   v     ^ *<      * v       ^ * *>*>* * v ^   v ^ * *<* * * v   ^ v ^ *>*>* *>*

Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).

Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 10⁹+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N² всех тестов не превысит 2⋅10⁴.


Входные данные: 
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.

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

Выходные данные: 
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 8 0 SS....RR 00100000 00100000 00011000 00000100 00000100 00000011 00000000 00000000 13 0 SSS.RRRSS.RR. 0001000000000 0001000000000 0001000000000 0000111000000 0000000000000 0000000000000 0000000000000 0000000001000 0000000001000 0000000000110 0000000000000 0000000000000 0000000000000	4 12	Для первого теста ребра таковы 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8. Имеется четыре схемы маршрутизации: 1→3→4→6→7,2→3→5→6→8 1→3→5→6→7,2→3→4→6→8 1→3→4→6→8,2→3→5→6→7 1→3→5→6→8,2→3→4→6→7 Для второго теста 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12. Одна из возможных схем маршрутизации: 1→4→5 2→4→7 3→4→6 8→10→12 9→10→11 В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
2	2 5 1 SS.RR 00101 00100 10010 00000 00000 6 2 S....R 001000 000100 010001 000010 001000 000000	3 1	Для первого теста, ребра 1→3,1→5,2→3,3→1,3→4. имеется три схемы маршрутизации: 1→3→1→5, 2→3→4 1→3→4, 2→3→1→5 1→5, 2→3→1→3→4 Для второго теста 1→3,2→4,3→2,3→6,4→5,5→3. Имеется только одна схема мартшрутизации: 1→3→2→4→5→3→6.
3	5 3 2 RS. 010 101 100 4 2 .R.S 0100 0010 1000 0100 4 2 .SR. 0000 0011 0100 0010 5 2 .SSRR 01000 10101 01010 00000 00000 6 2 SS..RR 001010 000010 000010 000010 100101 000000	2 1 2 6 24

Беси расположена на сети из N (2≤N≤10⁵) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[p_v,1,p_v,2,p_v,3,p_v,4].

Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,p_v,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:

Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,p_v,2), то Вы можете переключиться чтобы использовать портал (v,p_v,1) и обратно. Аналогично, если Ваше текущее положение (v,p_v,3) Вы можете переключиться на портал (v,p_v,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) p_v,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤c_v≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.

Например, если Вы переставить порталы вершины v в порядке [p_v,3,p_v,1,p_v,2,p_v,4], Это означает. что если Вы в вершине v,

Если Вы в портале p_v,1, Вы можете переключиться на портал p_v,3 и обратно
Если Вы в портале p_v,2, Вы можете переключиться на портал p_v,4 и обратно
Теперь Вы не можете переключаться с портала p_v,1 на p_v,2, или с портала p_v,3 на портал p_v,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.

Входные данные: 
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел c_v,p_v,1,p_v,2,p_v,3,p_v,4.
Гарантируется, что для каждой v все p_v,1,p_v,2,p_v,3,p_v,4 различны, и каждый портал появляется в списках ровно двух вершин.

Выходные данные: 
Одна строка содержит минимальное количество мунов требуемых для модификации сети чтобы сделать возможным достижимость каждого состояния из другого состояния.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3].

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами x_i и y_i (0≤x_i,y_i≤10⁴).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p₁,p₂,…,p_N из N точек
Она рисует отрезки между p₁ и p₂, p₂ и p₃, p₃ и p₁.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от p_i до p_j для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 10⁹+7.

Входные данные: 
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа x_i и y_i.

Выходные данные: 
Количество перестановок по модулю 10⁹+7.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 4 1 1 1 2	0	Никакая перестановка не сработает.
2	4 0 0 0 4 4 0 1 1	24	Все перестановки работают.
3	5 0 0 0 4 4 0 1 1 1 2	96	Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1). Для этой перстановки Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0). Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2). Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1). Рисунок: Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.

Коровы Фермера Джона ежедневно собираются на видео-платформе "mooZ". Они придумали простую числовую игру.
У Эльзы есть три положительных целых числа A, B, C (1≤A≤B≤C). Предполагается что они секретные, поэтому она не объявляет их явно своей сестре Беси. Вместо этого она говорит Беси N (4≤N≤7) различных целых чисел x₁,x₂,…,x_N (1≤x_i≤10⁹), подразумевая что каждое из xi это одно из чисел A, B, C, A+B, B+C, C+A, or A+B+C. Однако Эльза может солгать. Целые числа xi могут не соответствовать ни одной корректной тройке (A,B,C).

Беси попросила Вас определить количество троек (A,B,C), соответствующих числам, которые представила Эльза (возможно 0).

Каждый входной файл будет содержать T (1≤T≤100) тестов, которые необходимо обрабатывать независимо.

ФОРМАТ ВВОДА 
Первая строка содержит целое число T.
Каждый тест начинается с числа N, количества целых числе, которые Эльза дала Беси.

Вторая строка каждого теста содержит N различных целых чисел x₁,x₂,…,x_N.

ФОРМАТ ВЫВОДА 
Для каждого теста выведите количество троек (A,B,C), соответствующих представленным Эльзой числам.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 7 1 2 3 4 5 6 7 4 4 5 7 8 4 4 5 7 9 4 4 5 7 10 4 4 5 7 11 4 4 5 7 12 4 4 5 7 13 4 4 5 7 14 4 4 5 7 15 4 4 5 7 16	1 3 5 1 4 3 0 0 0 1	Для x={4,5,7,9}, имеется 5 возможных комбинаций: (2,2,5),(2,3,4),(2,4,5),(3,4,5),(4,5,7).

Беси учится на PhD в компьютерных науках. Она опубликовала N статей (1≤N≤10⁵) и её i-ую статью цитировали c_i раз (0≤c_i≤10⁵).

Беси слышала что академические успехи измеряются h-индексом. h-индекс - это наибольшее число h такое, что ученый имеет не менее h статей, каждая из которых цитируется не менее h раз. Например, учёный у которого четрые статьи с количествами цитат (1,100,2,3) имеет h-индекс равный 2, а ученый с количествами цитат (1,100,3,3) имеет h-индекс равный 3.

Чтобы повысить свой h-индекс Беси планирует написать обзорную статью, цитирующую некоторые из её прошлых статей. В связи с ограничением на количество страниц, она может включить не более L цитат в свой обзор (0≤L≤10⁵), т конечно она может процитировать каждую из своих статей не более одного раза.

Помогите Беси определить максимальный h-индекс, который она может достичь написанием своей обзорной статьи.

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

ФОРМАТ ВВОДА
Первая строка ввода содержит N и L.

Вторая строка ввода содержит N разделённых одиночными пробелами целых чисел c1,…,cN.

ФОРМАТ ВЫВОДА
Максимальный h-индекс, который Беси может получить написанием обзорной статьи.

№	Входные данные	Выходные данные	Пояснение
1	4 0 1 100 2 3	2	Беси не может цитировать свои статьи. Как указано ранее её h-индекс для (1,100,2,3) равен 2.
2	4 1 1 100 2 3	3	Если Беси процитирует третью статью, её количества цитирований станут (1,100,3,3). Как отмечено ранее, h в этом случае равен 3.