已经没有什么好害怕的了

已经使 Madoka 有签订契约，和自己一起战斗的想法后，Mami 忽然感到自己不再是孤单一人了呢。 于是，之前的谨慎的战斗作风也消失了，在对 Charlotte 的傀儡使用终曲——Tiro Finale 后，Mami 面临着即将被 Charlotte 的本体吃掉的局面。 这时，已经多次面对过 Charlotte 的 Homura 告诉了学 OI 的你这样一个性质：Charlotte 的结界中有两种具有能量的元素，一种是“糖果”，另一种是“药片”，各有 $n$ 个。在 Charlotte 发动进攻前，“糖果”和“药片”会两两配对，若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 $k$ 组，则在这种局面下，Charlotte 的攻击会丟失，从而 Mami 仍有消灭 Charlotte 的可能。 你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数.

第一行两个整数 $n,k$，含义如题目所描述。 接下来一行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个糖果的能量。 接下来 $n$ 个整数，第 $j$ 个数表示第 $j$ 个药片的能量。 保证上面两行不会有重复的数字。

一个答案，表示消灭 Charlotte 的情况个数，需要对 $10^9+9$ 取模。

4 2
5 35 15 45
40 20 10 30

4

【样例解释】 正确的组合为： (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). 【数据范围】 对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le k \le n$。