<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

544. Chess Championship
Time limit per test: 3 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Chess Championship is set up in the New Basyuki City. Two national teams, of Berland and Byteland, are going to have a match there. Each team is represented by n players. The championship consists of n games — in each game a pair of players from different teams meets. A game victory brings 1 point to the team and a game defeat doesn't add or subtract points.

The championship starts with the sortition — the process that determines opponent pairs. Each player from the first team plays with exactly one player from the second team (and vice versa).

A recent research conducted by Berland scientists showed that every player of either team is characterized by a single number — the level of his chess mastership. No two people among the 2n players play at the same level. Funny as it is, the game winner always is the player with the higher level.

The contest organizers received information that a high-ranking Berland official Mr. B. bet 100500 burles on the victory of his team with a k points gap. Immediately an unofficial "recommendation" came from very important people to "organize" the sortition so that the Berland team gets exactly k points more than the Byteland team.

Write a program that finds the number of distinct sortition results after which Berland gets exactly k points more than Byteland. Two sortitions are considered distinct if there is such player, that gets different opponents by the sortitions' results.

Input
The first line contains a pair of integers n and k (1 ≤ n ≤ 500; 1 ≤ k ≤ n) — the number of participants in each team and the required gap in points that Berland must win. The second and the third input lines contain n integers each: the i-th number of the second line characterizes the i-th Berland player's chess mastership level, and the j-th number of the third line characterizes the j-th Byteland player's chess mastership level. It is guaranteed that all numbers that characterize mastership levels are distinct integers from 0 to 109.

Output
Print a single integer — the number of ways to set up the sortition so that the Berland team wins k points more than the Byteland team in the championship. The answer can be rather large, so print it modulo 1000000009 (109+9).

Example(s)
sample input
sample output
4 2
5 35 15 45
40 20 10 30
4

sample input
sample output
2 2
3 4
1 2
2



Note
In the first example the acceptable sortition results are: (5-40, 35-20, 15-10, 45-30), (5-40, 45-20, 15-10, 35-30), (45-40, 5-20, 15-10, 35-30) and (45-40, 35-20, 15-10, 5-30).

<|response|>
1) Abridged problem statement
- There are two teams, Berland (A) and Byteland (B), each with n players. Every player has a distinct skill; the stronger player always wins.
- A sortition is a perfect matching between A and B (each A plays exactly one B).
- Count the number of sortitions in which Berland wins exactly k more games than Byteland, modulo 1,000,000,009.

2) Key observations
- Let wins(A) and wins(B) be the total wins of the two teams. Then:
  - wins(A) + wins(B) = n
  - wins(A) − wins(B) = k
  - Hence wins(B) = (n − k) / 2 and wins(A) = (n + k) / 2. If n − k is odd or k > n, the answer is 0.

- Sort all 2n players by skill (ascending), labeling each as team A or B.
  - Any match connects a weaker earlier player with a stronger later player.
  - When scanning left-to-right, the current player (as the stronger endpoint) can be matched only with an earlier unmatched opponent of the opposite team.

- DP idea while scanning:
  - Let cnt_a, cnt_b be the counts of A and B seen so far (in the already processed prefix).
  - Let dp[wa][wb] = number of ways such that wa A-wins and wb B-wins have already been formed within this prefix.
  - Unmatched earlier A's = cnt_a − (wa + wb), unmatched earlier B's = cnt_b − (wa + wb).

- Transition for the current player of team T:
  - Option 1: Leave current player unmatched (will serve as the weaker endpoint later).
    - dp'[wa][wb] += dp[wa][wb].
  - Option 2: Match current player now (as stronger) with an earlier unmatched opponent of the other team:
    - If T = A: candidates = cnt_b − (wa + wb). For each choice, we form an A-win:
      - dp'[wa + 1][wb] += dp[wa][wb] × candidates.
    - If T = B: candidates = cnt_a − (wa + wb). We form a B-win:
      - dp'[wa][wb + 1] += dp[wa][wb] × candidates.
  - Only apply Option 2 when candidates > 0.

- Final answer is dp[(n + k)/2][(n − k)/2] modulo 1e9+9.

- Complexity:
  - States: (wins(A)+1) × (wins(B)+1) ≤ ((n+1)/2)².
  - Steps: 2n (scan all players).
  - Time: O(n · wins(A) · wins(B)) = O(n^3) in the worst case, fine in C++.
  - Memory: O(wins(A) · wins(B)).

3) Full solution approach
- Compute wins(B) = (n − k) / 2 and wins(A) = (n + k) / 2. If (n − k) is odd or k > n, print 0.
- Merge both teams' skills into one list of pairs (skill, team), with team = 0 for A and 1 for B, and sort by skill ascending.
- Initialize dp[0][0] = 1; cnt_a = cnt_b = 0.
- For each player in sorted order:
  - Create a fresh new_dp table filled with 0.
  - For every state (wa, wb) with dp[wa][wb] > 0:
    - Leave unmatched: new_dp[wa][wb] += dp[wa][wb].
    - Match now:
      - If team == A:
        - candidates = cnt_b − (wa + wb).
        - If candidates > 0 and wa + 1 ≤ wins(A): new_dp[wa + 1][wb] += dp[wa][wb] × candidates.
      - If team == B:
        - candidates = cnt_a − (wa + wb).
        - If candidates > 0 and wb + 1 ≤ wins(B): new_dp[wa][wb + 1] += dp[wa][wb] × candidates.
    - Take all additions modulo 1e9+9.
  - Assign dp = new_dp.
  - Update cnt_a or cnt_b according to the current player's team.
- Output dp[wins(A)][wins(B)].

Why this works:
- Sorting ensures every pair connects an earlier weaker player to a later stronger player.
- At each step, either the current (stronger than all earlier) is matched to an earlier unmatched opponent (counted by "candidates"), or left for a future stronger player to match with.
- The counts of unmatched earlier A's/B's are precisely cnt_a − (wa + wb) and cnt_b − (wa + wb), because wa + wb pairs have consumed that many from each team in the prefix.
- This DP enumerates each valid perfect matching exactly once.

4) C++ implementation with comments

```cpp
#include <bits/stdc++.h>
#include <vector>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int mod = (int)1e9 + 9;

void mod_add(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}

int n, k;
vector<int> a, b;

void read() {
    cin >> n >> k;
    a.resize(n);
    b.resize(n);
    cin >> a >> b;
}

void solve() {
    // We want the number of wins by team A to be k more
    // than the number of wins of team B. We know that
    // wins(A) + wins(B) = n, so 2 * wins(B) + k = n, or
    // wins(B) = (n - k) / 2. The constraints in this problem
    // should immediately lead us to think about DP solutions.
    // Before we start with the actual idea, lets sort the individual
    // strengths (the a and b arrays), as we are anyways considering
    // permutations. In particular, we will create a joint sequence
    // of length 2 * n, that will contain all people and sort it. Then
    // we are essentially interested in ways of matching up positions
    // of this joint sequence such that we have exactly wins(B). To do
    // this we will consider the following DP state:
    //
    //    dp[prefix][wins(A) so far][wins(B) so far]
    //      - We are looking at prefix of the corresponding length.
    //      - Team A has claimed wins(A) wins from complete matches.
    //      - Team B has claimed wins(B) wins from complete matches.
    //
    // In particular, when we are at position i, we can either match
    // an existing pair, or start a new one. The state has enough
    // information for us to determine the number of unmatched
    // As and Bs - in particular we have wins(A) + wins(B) matched
    // elements of each A and B, and we know how many As and Bs there
    // are in the current prefix. Note that we multiply by the number of
    // valid candidates only when we "finish" the pair to avoid over counting.
    //
    // This has O(N^3) time complexity, but we can notice that we can only keep
    // two rows in the first dimension.

    int win_b = (n - k);
    if(win_b % 2 == 1) {
        cout << 0 << endl;
        return;
    }

    win_b /= 2;
    int win_a = win_b + k;

    vector<pair<int, int>> elements;
    for(int i = 0; i < n; i++) {
        elements.push_back({a[i], 0});
        elements.push_back({b[i], 1});
    }

    sort(elements.begin(), elements.end());

    int cnt_a = 0, cnt_b = 0;
    vector<vector<int>> dp(win_a + 1, vector<int>(win_b + 1, 0));
    dp[0][0] = 1;

    for(auto [val, type]: elements) {
        vector<vector<int>> new_dp(win_a + 1, vector<int>(win_b + 1, 0));
        for(int curr_win_a = 0; curr_win_a <= win_a; curr_win_a++) {
            for(int curr_win_b = 0; curr_win_b <= win_b; curr_win_b++) {
                if(!dp[curr_win_a][curr_win_b]) {
                    continue;
                }

                mod_add(
                    new_dp[curr_win_a][curr_win_b], dp[curr_win_a][curr_win_b]
                );

                int new_win_a = curr_win_a, new_win_b = curr_win_b;
                int candidates = -(curr_win_a + curr_win_b);
                if(type == 0) {
                    candidates += cnt_b;
                    new_win_a++;
                } else {
                    candidates += cnt_a;
                    new_win_b++;
                }

                if(candidates < 0) {
                    continue;
                }

                if(new_win_a <= win_a && new_win_b <= win_b) {
                    mod_add(
                        new_dp[new_win_a][new_win_b],
                        dp[curr_win_a][curr_win_b] * 1ll * candidates % mod
                    );
                }
            }
        }

        dp = std::move(new_dp);
        if(type == 0) {
            cnt_a++;
        } else {
            cnt_b++;
        }
    }

    cout << dp[win_a][win_b] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5) Python implementation with comments

```python
import sys

MOD = 1_000_000_009

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    k = int(next(it))
    a = [int(next(it)) for _ in range(n)]
    b = [int(next(it)) for _ in range(n)]

    # wins(B) = (n - k) / 2 must be integer, else 0
    if (n - k) % 2 != 0:
        print(0)
        return

    win_b = (n - k) // 2
    win_a = win_b + k  # (n + k) // 2

    # Build combined list: (strength, team), team: 0 = A (Berland), 1 = B (Byteland)
    elements = [(x, 0) for x in a] + [(x, 1) for x in b]
    elements.sort()  # increasing by strength

    # dp[wa][wb] = ways after processing the current prefix
    # to have formed wa A-wins and wb B-wins.
    dp = [[0] * (win_b + 1) for _ in range(win_a + 1)]
    dp[0][0] = 1

    cnt_a = 0  # how many A's seen so far (in the prefix before current element)
    cnt_b = 0  # how many B's seen so far

    for value, team in elements:
        # new dp after incorporating this current element
        new_dp = [[0] * (win_b + 1) for _ in range(win_a + 1)]

        # Traverse all states of formed wins so far
        for wa in range(win_a + 1):
            row = dp[wa]
            new_row_same = new_dp[wa]  # small speed-up by caching
            for wb in range(win_b + 1):
                ways = row[wb]
                if ways == 0:
                    continue

                # Option 1: leave current element unmatched
                new_row_same[wb] = (new_row_same[wb] + ways) % MOD

                # Option 2: match current (as stronger) with an earlier unmatched opponent
                # Number of earlier unmatched opponents of the opposite team:
                # equals (count_opposite_in_prefix) - (#pairs_already_closed),
                # where #pairs_already_closed = wa + wb.
                if team == 0:
                    # current is A, can close with B
                    candidates = cnt_b - (wa + wb)
                    if candidates > 0 and wa + 1 <= win_a:
                        new_dp[wa + 1][wb] = (new_dp[wa + 1][wb] + ways * candidates) % MOD
                else:
                    # current is B, can close with A
                    candidates = cnt_a - (wa + wb)
                    if candidates > 0 and wb + 1 <= win_b:
                        new_dp[wa][wb + 1] = (new_dp[wa][wb + 1] + ways * candidates) % MOD

        dp = new_dp

        # Update counts of seen players for the next iteration
        if team == 0:
            cnt_a += 1
        else:
            cnt_b += 1

    print(dp[win_a][win_b] % MOD)

if __name__ == "__main__":
    solve()
```

Note: The algorithm is O(n * win_a * win_b) ≈ O(n^3) in the worst case; this is easily fast in C++, but Python may be slow at the upper limits. The implementation is faithful to the intended solution.
