Problem C. 排列计数1 (counta.c/cpp)

Time limit: 1 second Memory limit: 256 megabytes

问题描述

给定两个排列 $P = (P_1, P_2, . . . , P_n)$ $Q = (Q_1,Q_2, . . . ,Q_n)$ 。 定义$F(P,Q) = \sum_{i=1}^{n}[P _i > Q_i]$, 其中$[]$ 表示，当括号中的表达式为真时，取值为1，否则取值为0, 即P 中比Q 中对应位置大的位置有$F(P,Q)$个。 由于小洞年事已高，所以他并不能完全记起P,Q 中每个位置的值。他将它忘记的位置用0 替代，他希望你能告诉他，又多少种方案将0 部分补全，使得$P,Q$ 均为合法的排列，同时$F(P,Q) = K$。

Input

一行两个整数$n,K$ 接下来两行，每行$n$个正整数或$0$，表示小洞的排列，其中前一行为$P$，后一行为$Q$

Output

输出一个整数，表示方案数对$10^9 + 7$取模的结果。

输入样例1:

4 2
4 2 0 0
0 0 4 2

输出样例1:

2

Notes

对20% 的数据，$n ≤ 10$ 对50% 的数据，$n ≤ 20$ 对70% 的数据，$n ≤ 200$ 对100% 的数据，$n ≤ 4000,K ≤ n$，保证$P_i$和$Q_i$ 不会同时为0。