题目描述

小x在搭积木。

她的积木有$n$行$m$列。

小x迷迷糊糊的，所以他只记得自己的积木从正面看和从侧面看的样子。

现在，小x想要知道有多少种方案符合他的观察。

输入格式

从标准输入读入数据。

第一行两个正整数$n,m$。

接下来一行$n$个整数，表示小x正面观察到的高度。

接下来一行$m$个整数，表示小x侧面观察到的高度。

输出格式

输出到标准输出。

一行$1$个正整数，表示不同的方案对$10^9+9$取模的值。

样例

输入

4 5
5 2 4 1
5 2 4 0 1

输出

429287

子任务

对于$20\%$的数据，$n,m\leq 10$。

对于$40\%$的数据，$n,m\leq 50$。

对于$100\%$的数据，$n,m\leq 200$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载