题目描述

给出 $n$ 个数 $a_i$，再给出 $n$ 个数 $b_i$，要求 $a$ 的数 和 $b$ 的数 两两配对，使得 $a > b$ 的对数 减去 $a < b$ 的对数 恰好等于 k 的方案数。

输入格式

第一行两个整数 $n \ k \ (1 \le n \le 2000，0 \le k \le n)$。

下来 $n$ 个整数 $a_i$。

下来 $n$ 个整数 $b_i$。

保证上面两行不会有重复的数字。

输出格式

一个答案，需要对 $10^9+9$ 取模。

输入输出样例 #1

样例输入 #1

4 2
5 35 15 45
40 20 10 30

样例输出 #1

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).