已经没有什么好害怕的了

题目描述

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

输入输出格式

输入格式


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

输出格式


一个答案,表示消灭Charlotte的情况个数,要 mod (10^9 + 9)

输入输出样例

输入样例 #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). 【数据范围】 对于100%的数据:l<=n<=_2000,0<=k<=n