Сортування "бульбашкою"
Сортуваня простими обмінами, сортування бульбашкою (англ. bubble sort) — простий алгоритм сортування. Для розуміння і реалізації цей алгоритм — найпростіший, але эфективний він лише для невеликих масивів. Алгоритм вважається навчальним і практично не застосовується поза межами начальної літератури, замість нього на практиці застосовується сортування вставками. Алгоритм полягає у повторюваних проходах по масиву, що сортується. За кожен прохід елементи послідовно порівюються попарно і, якщо порядок у парі невірний, виконується обмін елементів. Проходи по масиву повторюються до тих пір, доки на черговому проході не виявиться, що обміни більше не потрібні, що означає — масив вісортовано. При проході алгоритму, елемент, який стоїть не на свому місці, «спливає» до потрібної позиції як бульбашка у воді, звідси і назва алгоритму.
ВікіпедіЯ
Булбашове сортування є дуже простим алгоритмом і його часова складність складає O(n^2). Кожен раз, проходячи по всьому масиву, спочатку ми порівнюємо сусідні елементи і якщо є потреба міняємо їх місцями. Цей процес повторюється, поки при черговому проході зроблено хоча б одну заміну. Припустимо, що після T проходів масив вже відсортовано у порядку зростаня, тоді ми говоримо, що T є кількістю етапів сортування для заданого массиву. Нижче наведено приклад. Візьмемо за заданий початковий масив "5 1 4 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 (T ≤ 100000), яке вказує кількість тестових випадків.
Наступні T рядкі містять тестові дані. У кожному рядку знаходиться два цілих числа N і K (1 ≤ N ≤ 1000000, 0 ≤ K ≤ N - 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 проходи алгоритму сортування бульбашкою.