Шедевр
Після створення геніального "Пурпурного квадрата" та нетрадиційного "Фуксійського круга", всесвітньо відомий художник Теодор Кадман Спенсер працює над своїм наступним шедевром. Цього разу великий майстер дійсно перевершив самого себе, адже цей витвір мистецтва буде невимовним з точки зору єдиної геометричної форми, що, безсумнівно, є кроком вперед на шляху Теодора до завершення.
Маестро вирішив використати величезне полотно у формі квадрата розміром n на n, ідеально розділене на квадрати розміром 1 на 1. Спочатку тканина повністю біла, і художник починає використовувати свій пензель, щоб намалювати темно-бордові квадрати.
Ідея Теодора полягає в тому, щоб розпочати з верхнього лівого кута полотна (тобто з першого рядка і першого стовпця) і обережно рухатися до правого нижнього кута, завжди переміщуючись або на один квадрат праворуч, або на один квадрат вниз. Усі квадрати, яких торкнувся пензель, одразу ж стають бордовими. Але це ще не кінець плану геніального художника! Як тільки він добирається до правого нижнього кута, він повертається, рухаючись ліворуч або вгору, щоб, нарешті, закінчити на квадраті, з якого почав. Художник вільний обирати свій шлях так, як йому заманеться, а поля, які фарбуються двічі, не змінюють свій зовнішній вигляд.
Ви пристрасний шанувальник робіт Спенсера і початківець хакер, не в змозі протистояти спокусі проникнути в комп'ютер художника і спробувати завантажити плани його шедевра. Однак величезний розмір файлу зробив це неможливим, тому ви швидко стиснули його наступним чином. Для кожного з n рядків ви обчислили кількість бордових квадратів у ньому, а потім зробили те ж саме для кожного з n стовпців. Нарешті, ви зберегли ці значення на своєму локальному сервері, завершивши справу, не будучи спійманим.
Тепер ви незадоволені — хотілося б знати точний процес, який приведе до створення шедевра, і вам байдуже на стиснуту форму, яку отримали. Що все це вам говорить? Обчисліть кількість різних шляхів пензля, які відповідають наявній у вас інформації. Два шляхи вважаються різними, якщо в якийсь момент художник обирає інший напрямок. Зверніть увагу, що два різних шляхи можуть привести до однієї й тієї ж картини, але ви настільки сильно дбаєте про процес, що вважаєте їх різними.
Оскільки відповідь може виявитися великою, виведіть її за модулем 10^9 + 7.
Вхідні дані
Перша строка містить кількість тестів z (1 ≤ z ≤ 30). Далі слідують описи тестів.
Перша строка кожного тесту містить розмір полотна n (1 ≤ n ≤ 100 000). Друга строка містить n цілих чисел r[i] (0 ≤ r[i] ≤ n) — кількість темно-бордових квадратів у кожному рядку картини. У наступній строкі задані описи стовпців у тому ж форматі.
Вихідні дані
Для кожного тесту виведіть одне ціле число: кількість шляхів, які призводять до малювання відповідно до заданої інформації за модулем 10^9 + 7.