Bubble Sort

Bubble sort is a simple sorting algorithm. For understanding and implementation, this algorithm is one of the simplest, but it is only effective for small arrays. It is mostly used for educational purposes and rarely applied outside teaching; in practice, insertion sort is more common. The algorithm repeatedly passes through the array to be sorted. During each pass, adjacent elements are compared and, if necessary, swapped. The passes continue until no swaps are required, indicating the array is sorted. As the algorithm proceeds, elements "bubble" up to their correct positions, hence the name of the algorithm.

Wikipedia

Bubble Sort is a very simple algorithm with a time complexity of O(n^2). Each time, starting from the beginning of the array, we compare adjacent elements and, if needed, swap them. This process is repeated until in one of the passes no swaps were made. Suppose that after $T$ passes the array is already sorted in ascending order. Then we say that $T$ is the number of Bubble Sort Rounds for the given array. Below is an example. Take the starting array $51428$ and sort it using Bubble Sort as follows:

First pass:

(5\ 1\ 4\ 2\ 8) \to (1\ 5\ 4\ 2\ 8), compared the first two elements and swapped them. (1\ 5\ 4\ 2\ 8) \to (1\ 4\ 5\ 2\ 8), swap since 5 > 4. (1\ 4\ 5\ 2\ 8) \to (1\ 4\ 2\ 5\ 8), swap since 5 > 2. (1\ 4\ 2\ 5\ 8) \to (1\ 4\ 2\ 5\ 8), last two elements are already ordered (8 > 5), so no swap occurs.

Second pass:

(1\ 4\ 2\ 5\ 8) \to (1\ 4\ 2\ 5\ 8). (1\ 4\ 2\ 5\ 8) \to (1\ 2\ 4\ 5\ 8), swap since 4 > 2. (1\ 2\ 4\ 5\ 8) \to (1\ 2\ 4\ 5\ 8). (1\ 2\ 4\ 5\ 8) \to (1\ 2\ 4\ 5\ 8).

After T = 2 passes, the array is sorted, therefore, the number of Bubble Sort rounds for this array is $2$.

A sorted array $A$ consisting of $N$ distinct integers is given. It is claimed that it was obtained after exactly $K$ passes of Bubble Sort. Task: How many initial arrays $A$ could there be so that after exactly $K$ passes of Bubble Sort, the sorted array is obtained? The result may be very large, so output the answer modulo $20100713$.