|
Арифметика и логика
(Время: 0,25 сек. Память: 32 Мб Сложность: 88%)
Готовясь к математическому кружку, учитель раздал Анечке и остальным ученикам специальную учебную ленту. В классе Q учеников. На длинной полоске закреплены N карточек, расположенных слева направо. Карточки прикреплены к ленте маленькими кольцами, поэтому их нельзя снять или переставить – порядок карточек фиксирован. Каждая карточка двусторонняя. С одной стороны написана задача по арифметике, а с другой – логическая задача. У каждой задачи есть уровень сложности – целое число от 1 до P. Чем больше число, тем задача труднее. Карточка закреплена так, что её можно повернуть вокруг кольца. Тогда карточка просто переворачивается, и стороны меняются местами. Никаких других действий с карточками сделать нельзя. Анечка решает задания, двигаясь по ленте слева направо. Ей удобно заниматься, если задания становятся не легче предыдущих.
Анечка может перевернуть некоторые карточки, чтобы попытаться добиться такого расположения. Однако это удаётся не всегда. Например, если карточек две и на них записаны сложности арифметика: (3, 1) и логика: (1, 2), то какие бы карточки ни переворачивали, обязательно получится, что встретится более лёгкая задача после более сложной.
По заданным числам N и P определите, сколько существует различных наборов карточек, для которых Анечка и другие ученики смогут переворотами некоторых карточек добиться такого порядка заданий.
Входные данные
Входной файл INPUT.TXT в первой строке содержит натуральное число Q. Далее в каждой строке по два натуральных числа: N, P (1 ≤ Q ≤ 1000;1 ≤ min(N, P) ≤ 200; 1 ≤ max(N, P) ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ для каждого ученика по модулю 109 + 7.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 2
2 1
2 2 | 4
1
11 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
