502013 - 补给

【题目描述】补给

探险队在准备探险的补给方案,即给定n和k,已知n个葡萄糖能量ai和n个维生素药片能量bi,每个ai和bi互不相等。将葡萄糖和维生素药片一一对应,求恰好葡萄糖比维生素药片能量大的组数比“药片”比“葡萄糖”能量大的组数多k 组的方案数。

Input

第一行两个整数n和k(1≤n≤2000,0≤k≤n)。 接下来一行n个整数,第i个数表示第i个葡萄糖的能量。 接下来n个整数,第j个数表示第j个维生素药片的能量。 保证上面两行不会有重复的数字。

Output

一个答案,表示方案数,需要对10^9+9取模。

Examples

Input

4 2
5 35 15 45
40 20 10 30

Output

4

Hint

方案为:(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)。

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题