Problem Description

After making Madoka want to sign a contract and fight together, Mami suddenly felt that she was no longer alone.

So her previously cautious fighting style disappeared. After using the finale—Tiro Finale—on Charlotte’s puppet, Mami ended up in a situation where she was about to be eaten by Charlotte’s true body.

At this moment, Homura, who has faced Charlotte many times, told you, who study OI, the following property: In Charlotte’s barrier, there are two kinds of energy-bearing elements: “candies” and “pills”, $n$ of each. Before Charlotte launches an attack, the “candies” and “pills” will be paired up one-to-one. If the number of pairs where the candy’s energy is greater than the pill’s energy is exactly $k$ more than the number of pairs where the pill’s energy is greater than the candy’s energy, then in this situation, Charlotte’s attack will miss, and Mami will still have a chance to destroy Charlotte.

You must, based on the energy information of the “candies” and “pills” that Homura tells you, quickly tell Homura how many such situations there are.

Input Format

The first line contains two integers $n,k$, with meanings as described in the statement.

The next line contains $n$ integers. The $i$-th number represents the energy of the $i$-th candy.

The next line contains $n$ integers. The $j$-th number represents the energy of the $j$-th pill.

It is guaranteed that there are no duplicate numbers within each of the above two lines.

Output Format

Output one integer, the number of situations in which Charlotte can be destroyed, modulo $10^9+9$.

4 2
5 35 15 45
40 20 10 30

4

Hint

[Sample Explanation]

The correct matchings 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),
(45-40,35-20,15-10,5-30).

[Constraints]
For $100\%$ of the testdata, $1 \le n \le 2000$, $0 \le k \le n$.

Translated by ChatGPT 5