云

(cloud.cpp 1s/512MB)

题目描述

小 Y 很喜欢以不同的角度去思考问题，就像喜欢站在不同的角度望云。这天，她的好朋友小 T 搬过来一个棋盘，棋盘上有 $n^2$ 个格子，排列成一个 $n\times n$ 的正方形，第 $i$ 行第 $j$ 列的格子用 $(i,j)$ 表示。小 T 还找来了 $m$ 个不同的棋子，依次编号为 $1,2,\cdots,m$，并把这 $m$ 个棋子放在了棋盘的格子里，保证每个格子上最多只有一个棋子。

小 Y 以两种不同的顺序遍历棋盘上的格子，一种是从上到下、从左往右，即先从左往右遍历第一行格子 $(1,1),\cdots,(1,n)$，再从左往右遍历第二行格子 $(2,1),\cdots,(2,n)$……最后从左往右遍历第 $n$ 行格子 $(n,1),\cdots,(n,n)$；另一种是从上到下、从右往左，即先从右往左遍历第一行格子 $(1,n),\cdots,(1,1)$……最后从右往左遍历第 $n$ 行格子 $(n,n),\cdots,(n,1)$。这样她就会以两种顺序经过棋盘上的 $m$ 个棋子，她把这两种经过顺序记为了两个长度为 $m$ 的数组 $a,b$，$a_i$ 表示第一种顺序下经过的第 $i$ 个有棋子的格子上的棋子的编号，$b_i$ 同理。现在她把这两个数组交给你，她想考考你原本的棋盘上的棋子有多少种可能的摆放方式。。两种棋子摆放方式被视为不同当且仅当存在某个编号的棋子所在的格子不同，由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。

当然，小 Y 的记性不太好，可能会出现没有任何一种摆放方式能得到这两个数组，此时你只需要输出 $0$。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $m$ 个两两不同的整数，依次为 $a_1,a_2,\dots ,a_m$。

第三行包含 $m$ 个两两不同的整数，依次为 $b_1,b_2,\dots ,b_m$。

保证 $a$ 与 $b$ 均为 ${1,2,\dots ,m}$ 的一种排列。

输出格式

输出一个整数，表示满足条件的棋子摆放方式总数。若不存在可行方式则输出 $0$。

输入输出样例 #1

输入 #1

3 4
1 2 3 4
2 1 3 4

输出 #1

27

输入输出样例 #2

输入 #2

2 3
1 2 3
3 1 2

输出 #2

0

数据范围

对于 $30\%$ 的数据，$n=3,m\le 9$。

对于 $70\%$ 的数据，$n\le 100,m\le 1000$。

另有 $10\%$ 的数据，$a_i=b_i$。

对于 $100\%$ 的数据，$n\le 5\times 10^3,m\le 5\times 10^5$。保证 $m\le n^2$。