e-olymp
Задачі

Сортування "бульбашкою"

Сортування "бульбашкою"

Сортуваня простими обмінами, сортування бульбашкою (англ. bubble sort) — простий алгоритм сортування. Для розуміння і реалізації цей алгоритм — найпростіший, але эфективний він лише для невеликих масивів. Алгоритм вважається навчальним і практично не застосовується поза межами начальної літератури, замість нього на практиці застосовується сортування вставками. Алгоритм полягає у повторюваних проходах по масиву, що сортується. За кожен прохід елементи послідовно порівюються попарно і, якщо порядок у парі невірний, виконується обмін елементів. Проходи по масиву повторюються до тих пір, доки на черговому проході не виявиться, що обміни більше не потрібні, що означає — масив вісортовано. При проході алгоритму, елемент, який стоїть не на свому місці, «спливає» до потрібної позиції як бульбашка у воді, звідси і назва алгоритму.

ВікіпедіЯ

Булбашове сортування є дуже простим алгоритмом і його часова складність складає O(n2). Кожен раз, проходячи по всьому масиву, спочатку ми порівнюємо сусідні елементи і якщо є потреба міняємо їх місцями. Цей процес повторюється, поки при черговому проході зроблено хоча б одну заміну. Припустимо, що після T проходів масив вже відсортовано у порядку зростаня, тоді ми говоримо, що T є кількістю етапів сортування для заданого массиву. Нижче наведено приклад. Візьмемо за заданий початковий масив "5 14 2 8" а потім використовуючи описаний алгоритм бульбашкового сортування проведемо його сортування наступним чином:

Перший прохід:

( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), порівняли перших два елементи і поміняли їх місцями.
( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), поміняли місцями 5 > 4
( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), поміняли місцями 5 > 2
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), так як два останніх елементи впорядковані (8 > 5), алгоритм не міняє їх місцями.

Другий прохід:

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), поміняли місцями 4 > 2
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

Після T = 2 проходів масив вже відсортовано, тому ми кажемо, що кількість проходів алгориму сортування бульбашкою для заданого масиву дорівнює 2.

Петрик вивчив алгоритм сортування бульбашкою у класі і його вчитель задає завдання, пов'язані з ним, як домашнє завдання. Вчитель надав Петрику вже відсортований масив A, яки складається з N різних цілих чисел і стверджує, що він отримав його після K проходів алгоримом сортування бульбашкою. Завдання: яка кількість заданих початкових масивів A може існувати, щоб в результаті отримати заданный масив після K проходів алгоритму сортування бульбашкою? Результат може бути дуже великим, тому його необхідно вивести по модулю 20100713.

Вхідні дані

Вхідні дані складаються з декількох тестів.

У першому рядку задано натуральне число T (T100000), яке вказує кількість тестових випадків.

Наступні T рядкі містять тестові дані. У кожному рядку знаходиться два цілих числа N і K (1N1000000, 0KN - 1) де N вказує на розмір масиву, а K - кількість етапів сортування алгоритмом бульбашки.

Вихідні дані

Для кожного тестового випадку вивести у окремому рядку відповідь на поставлену задачу по модулю 20100713.

Примітка

Препустимо, що задано масив {a, b, c} (a < b < c). Існує 6 різних варіантів початкового масиву:

{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a},

а заданий ми можемо отримати по різному:

{a, b, c}: не сортуючи, так як масив вже відсортовано.

{a, c, b}, {b, a, c}, {c, a, b}: за один прохід алгоритму сортування бульбашкою.

{b, c, a}, {c, b, a}: за 2 проходи алгоритму сортування бульбашкою.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
3
3 0
3 1
3 2
Вихідні дані
1
3
2