После гениального "Пурпурного квадрата" и нетрадиционного "Фуксийского круга" всемирно известный художник Теодор Кадман Спенсер работает над своим следующим шедевром. На этот раз великий мастер действительно превзошел самого себя, поскольку это произведение искусства будет неописуемым с точки зрения единой геометрической формы, что, несомненно, является шагом вперед в пути Теодора к завершению.

Маэстро решил использовать огромный холст в форме квадрата n - на - n, идеально разделенный на квадраты 1 - на - 1. Ткань изначально полностью белая, художник начинает использовать свою кисть, чтобы нарисовать темно-бордовые квадраты.

Идея Теодора состоит в том, чтобы поместить кисть в верхний левый угол холста (то есть в первый ряд и первый столбец) и осторожно двигать ее в правый нижний угол, всегда перемещая либо на один квадрат вправо, либо на один квадрат вниз. Все квадраты, к которым прикоснулась кисть, сразу же станут бордовыми. Но, как ни невероятно, это не конец плана гениального художника! Как только он добирается до правого нижнего угла, он возвращается, двигаясь влево или вверх, чтобы, наконец, закочить на квадрате, с которого начал. Художник свободен выбирать свой путь так, как ему заблагорассудится, а поля, которые окрашиваются дважды, не меняют их внешний вид.

Вы страстный поклонник работ Спенсера и начинающий хакер - не в силах противостоять побуждению войти в компьютер художника и попытались загрузить планы его шедевра. Однако огромный размер файла сделал это невозможным, поэтому Вы быстро сжали его следующим образом. Для каждой из n строк Вы вычислили количество бордовых квадратов в ней, а затем проделали то же самое для каждого из n столбцов. Наконец, Вы сохранили эти значения на своем локальном сервере, завершив дело не будучи пойманым.

Теперь Вы недовольны - хотелось бы знать точный процесс, который приведет к созданию шедевра, и Вам наплевать на сжатую форму, которую получили. О чем все это тебе говорит? Вычислите количество различных путей кисти, которые соответствуют имеющейся у Вас информации. Два пути считаются разными, если в какой-то момент художник выбирает другое направление. Обратите внимание, что два разных пути могут привести к одной и той же картине, но Вы настолько сильно заботитесь о процессе, что считаете их разными.

Поскольку ответ может оказаться большим, выведите его по модулю 109 + 7.

Входные данные

Первая строка содержит количество тестов z (1 ≤ z ≤ 30). Далее следуют описания тестов.

Первая строка каждого теста содержит размер холста n (1 ≤ n ≤ 100 000). Вторая строка содержит n целых чисел ri (0 ≤ ri ≤ n) - количество темно-бордовых квадратов в каждой строке картины. В следующей строке заданы описания столбцов в том же формате.

Выходные данные

Для каждого теста выведите одно целое число: количество путей, которые приводят к рисованию в соответствии с заданной информацией по модулю 109 + 7.