Сортировка "пузырьком"

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

Википедия

Пузырьковая сортировка является очень простым алгоритмом и его временная сложность составляет O(n^2). Каждый раз, проходя по всему массиву, сначала мы сравниваем соседние элементы и если есть необходимость меняем их местами. Этот процесс повторяется, пока при очередном проходе не будет ни одной замены. Предположим, что после $T$ проходов массив уже отсортирован в порядке возрастания, тогда мы говорим, что $T$ является количеством этапов сортировки для заданного массива. Ниже приведен пример. Возьмём в качестве начального массива "5 1 4 2 8" и, используя описанный алгоритм пузырьковой сортировки, отсортируем его следующим образом:

Первый проход:

($51$ 4 2 8) $\to$ ($15$ 4 2 8), сравнили первые два элемента и поменяли их местами. (1 $54$ 2 8) $\to$ (1 $45$ 2 8), обмен так как 5 $>$ 4. (1 4 $52$ 8) $\to$ (1 4 $25$ 8), обмен так как 5 $>$ 2. (1 4 2 $58$) $\to$ (1 4 2 $58$), последние два элемента уже упорядочены (8 $>$ 5), обмен не требуется.

Второй проход:

($14$ 2 5 8) $\to$ ($14$ 2 5 8). (1 $42$ 5 8) $\to$ (1 $24$ 5 8), обмен так как 4 $>$ 2. (1 2 $45$ 8) $\to$ (1 2 $45$ 8). (1 2 4 $58$) $\to$ (1 2 4 $58$).

После T = 2 проходов массив уже отсортирован, поэтому количество этапов сортировки пузырьком для данного массива равно $2$.

Дан уже отсортированный массив $A$ из $N$ различных целых чисел. Утверждается, что он был получен после ровно $K$ проходов сортировки пузырьком. Задача: сколько исходных массивов $A$ могло быть, чтобы после ровно $K$ проходов сортировки пузырьком был получен данный отсортированный массив? Ответ может быть очень большим, поэтому выведите его по модулю $20100713$.