D2. Финальный диалог (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии вам также нужно вывести количество оптимальных последовательностей операций. Вы можете делать взломы, только если обе версии задачи решены.

Даны массив $$$a$$$ длины $$$n$$$ и массив $$$b$$$ длины $$$m$$$ ($$$b_i > b_{i+1}$$$ для всех $$$1 \le i < m$$$). Изначально значение $$$k$$$ равно $$$1$$$. Ваша цель — сделать массив $$$a$$$ пустым, выполняя операции двух типов:

  • $$$1$$$ тип: Если значение $$$k$$$ меньше $$$m$$$ и массив $$$a$$$ не пуст, вы можете увеличить значение $$$k$$$ на $$$1$$$. Это не влечет за собой никаких затрат.
  • $$$2$$$ тип: Удалить непустой префикс массива $$$a$$$, такой, что его сумма не превосходит $$$b_k$$$. Стоимость этой операции равна $$$m - k$$$.

Вам нужно минимизировать суммарную стоимость последовательности операций, в результате которой массив $$$a$$$ станет пустым. Если сделать массив пустым невозможно, выведите $$$-1$$$. В противном случае выведите минимальную суммарную стоимость операций, а также количество последовательностей операций, имеющих минимальную стоимость. Так как это количество может быть очень большим, выведите остаток от его деления на $$$10^9 + 7$$$.

Две последовательности операций считаются различными, если на любом шаге выбран другой тип операции или отличается размер удаляемого префикса.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$\boldsymbol{1 \le n \cdot m \le 3 \cdot 10^5}$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Третья строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$). Гарантируется, что $$$b_i > b_{i+1}$$$ для всех $$$1 \le i < m$$$.

Гарантируется, что сумма $$$\boldsymbol{n \cdot m}$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных, если можно сделать $$$a$$$ пустым, выведите два целых числа. Первое должно быть минимальной общей стоимостью операций, а второе — количеством последовательностей операций, которые достигают этой минимальной стоимости, по модулю $$$10^9 + 7$$$.

Если не существует последовательности операций, которая делает $$$a$$$ пустым, то выведите одно число $$$-1$$$.

Пример
Входные данные
5
4 2
9 3 4 3
11 7
1 2
20
19 18
10 2
2 5 2 1 10 3 2 9 9 6
17 9
10 11
2 2 2 2 2 2 2 2 2 2
20 18 16 14 12 10 8 6 4 2 1
1 6
10
32 16 8 4 2 1
Выходные данные
1 3
-1
2 11
10 42
4 1
Примечание

В первом наборе входных данных существует $$$3$$$ оптимальных последовательностей операций, которые имеют стоимость $$$1$$$:

  • Все $$$3$$$ последовательности начинаются с операции типа $$$2$$$, удаляющей префикс $$$[9]$$$, чтобы сделать $$$a = [3, 4, 3]$$$, и данная операция имеет стоимость $$$1$$$. Затем мы выполняем операцию типа $$$1$$$, чтобы увеличить значение $$$k$$$ на $$$1$$$. Все последующие операции теперь имеют стоимость $$$0$$$.
  • Одна последовательность продолжается удалением префикса $$$[3, 4]$$$, затем $$$[3]$$$.
  • Другая последовательность продолжается удалением префикса $$$[3]$$$, затем $$$[4, 3]$$$.
  • Другая последовательность продолжается удалением префикса $$$[3]$$$, затем $$$[4]$$$, затем $$$[3]$$$.

Во втором наборе входных данных невозможно удалить ни одного префикса массива, так как $$$a_1 > b_1$$$, поэтому массив $$$a$$$ нельзя сделать пустым ни одной последовательностью операций.