题目描述

已经使 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\leq n\leq 2000$，$0\leq k\leq n$。

题目来源

2014 湖北省队互测 week2