Заповніть табличку

Limits: 2 sec., 512 MiB

У Зеника є масиви \(l\), \(r\) довжини \(n\), усі значення цих масивів від 0 до \(m\), а також масив \(d\) довжини \(m\), усі значення якого від 0 до \(n\).

Марічка може як-небудь переставляти елементи у кожному масиві. Також у Зеника є табличка розміром \(n \times m\), поділена на одиничні клітинки, усі клітинки якої спершу білі. Після цього Зеник зафарбовує у синій колір перші \(l_i\) клітинок та останні \(r_i\) клітинок у \(i\)-му рядку. А також Зеник зафарбовує нижні \(d_j\) клітинок у \(j\)-му стовпці.

Зеник хоче повністю зафарбувати усю табличку, але не використати забагато фарби, а отже зафарбувати кожну клітинку рівно один раз. Марічці ж цікаво, скільки існує способів переставити значення в кожному з масивів, щоб досягти цього. Два способи вважаємо різними, якщо існує хоча б один індекс хоча б одного масиву такий, що відповідні значення відрізняються. Оскільки способів може бути дуже багато, виведіть остачу від ділення кількості способів на \(10^9+7\).

Input

В першому рядку задано 2 цілі числа \(n\) та \(m\).

В другому рядку задано \(n\) цілих чисел \(l_i\).

В третьому рядку задано \(n\) цілих чисел \(r_i\).

В четвертому рядку задано \(m\) цілих чисел \(d_i\).

Output

Виведіть єдине число – остачу від ділення кількості способів на \(10^9+7\).

Constraints

\(1 \le n, m \le 2 \cdot 10^5\),

\(0 \le l_i, r_i \le m\),

\(0 \le d_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 0 1 2 0 1 1 1 1 2 3	1

Input (stdin) сopy	Output (stdout) сopy
4 7 4 4 0 0 3 3 7 7 0 0 0 0 0 0 0	6

Input (stdin) сopy	Output (stdout) сopy
1 1 1 0 1	0

Notes

Єдиний спосіб розфарбування у першому прикладі:

У другому прикладі є 6 способів, як переставити значення в масиві \(l\), для кожного з них існує єдиний варіант масивів \(r\) та \(d\).

У третьому прикладі неможливо виконати умову, адже клітинка буде зафарбована двічі.