SPOJ in Gyumri

   За один шаг Великий Уравнитель может совершать над натуральным числом N две операции:

• прибавить одно из заданных чисел a₁…a_k

• умножить на одно из заданных чисел b₁…b_s

   Определите, сколькими различными способами из числа N Великий Уравнитель может получить число M, если последним действием должно быть умножение. Два способа считаются различными, если они содержат различное количество операций или если на каком-то шаге использованное действие или число отличаются.

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

   Первая строка входных данных содержит одно число T – количество тестов (T ≤ 70). Далее идут описания тестов. Описание каждого теста начинается со строки, содержащей два натуральных числа N и M (1 ≤ N < M ≤ 10⁵). Следующая строка содержит целое число K (0 ≤ K ≤ 100). Если K > 0, то следующая строка содержит K натуральных чисел a₁…a_K (1 ≤ a_i ≤ 100). Следующая строка содержит целое число S (0 ≤ S ≤ 100). Если S > 0, то следующая строка содержит S натуральных чисел b₁…b_S (2 ≤ b_j ≤ 100). Гарантируется, что сумма (K+S) по всем тестам не превосходит 5000, сумма M по всем тестам не превосходит 13*10⁵.

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

   Для каждого теста в отдельной строке выведите одно число – количество способов, которым можно получить число M при том, что последним действием должно быть умножение. Ответ дать по модулю 10⁹.

Примеры