已经使Modoka有签订契约，和自己一起战斗的想法后，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的情况个数。答案可能会很大,所以mod (10⁹+9)

样例解释：
正确的组合为: (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)。

数据范围：
约定：给出的2*n个能量值两两不同
对于10%的数据：1<=n<=10
对于40%的数据：1<=n<=500
对于100%的数据：1<=n<=2000，0<=k<=n