题目描述
小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}$
