Insertion Sort vs Quicksort Comparisons

While studying data structures, Kkung grew tired of exercises that ask you to count the number of comparisons made by each sorting algorithm, so he decided to build the most vexing problem he could think of.

You are given two integers N and X. Among the permutations of the integers 1 through N, count those for which insertion sort makes more comparisons than quicksort, but at most X more. Formally, for a permutation let NI be the number of comparisons made by insertion sort and NQ the number made by quicksort; count the permutations that satisfy 1 <= NI - NQ <= X. Because the answer can be very large, print it modulo 1234567.

The pseudocode below is insertion sort, which also counts its comparisons. It uses a sentinel A[0] = -infinity.

procedure insertionSort(N, A[1..N]):
    A[0] := -infinity
    for i := 2 to N:
        j := i
        comparisons := comparisons + 1
        while A[j - 1] > A[j]:
            swap(A[j - 1], A[j])
            j := j - 1
            comparisons := comparisons + 1

The pseudocode below is quicksort. If the array being sorted has length L, its partition step performs L - 1 comparisons.

procedure quickSort(A):
    if length(A) <= 1:
        return A
    less := empty list
    greater := empty list
    pivot := A[1]
    for i := 2 to length(A):
        comparisons := comparisons + 1
        if A[i] < pivot:
            append A[i] to less
        else:
            append A[i] to greater
    return concatenate(quickSort(less), pivot, quickSort(greater))

For example, consider the permutation (3, 1, 4, 2). Insertion sort makes 6 comparisons in total (2 when i=2, 1 when i=3, and 3 when i=4). Quicksort makes 4 comparisons in total: with pivot 3 it makes 3 comparisons and splits into (1, 2) and (4); then (1, 2) needs 1 more comparison, for 4 comparisons overall.

The first line contains two integers N and X separated by a space.

• 1 < N < 32
• 1 <= X <= N^2

Print, on a single line, the number of permutations of 1 through N for which insertion sort makes at least 1 and at most X more comparisons than quicksort (that is, 1 <= NI - NQ <= X), taken modulo 1234567.

For N = 3, the six permutations together with their comparison counts (NI = insertion sort, NQ = quicksort) are as follows.

1 2 3 - NI = 2, NQ = 3
1 3 2 - NI = 3, NQ = 3
2 1 3 - NI = 3, NQ = 2
2 3 1 - NI = 4, NQ = 2
3 1 2 - NI = 4, NQ = 3
3 2 1 - NI = 5, NQ = 3

The differences NI - NQ are -1, 0, 1, 2, 1, 2 respectively. When X = 1, the permutations that satisfy 1 <= NI - NQ <= 1 are (2 1 3) and (3 1 2), so the answer is 2.