E. Корова и угощения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После удачного года по количеству удоя, Фермер Джон решил наградить своих коров их любимым угощением: вкусной травой!

На поле располагается ряд из $$$n$$$ единиц травы, каждая единица соответствующего уровня сладости $$$s_i$$$. У Фермера Джона $$$m$$$ коров, каждая обладает своим любимым уровнем сладости $$$f_i$$$ и уровнем голода $$$h_i$$$. Фермер Джон хочет выбрать непересекающиеся подмножества коров, чтобы разместить их с левой и правой стороны ряда травы. Нет никаких ограничений на количество коров с каждой стороны. Поведение коров описывается следующим образом:

  • Коровы с левой и правой сторон начинают кормиться по очереди в порядке, выбранном Фермером Джоном.
  • Кормежка коровы выглядит следующим образом: корова начинает двигаться к противоположному концу ряда, не меняя своего направления, и поедает траву своего любимого уровня сладости, пока не съест $$$h_i$$$ единиц.
  • В тот момент, как корова съест $$$h_i$$$ травы, она ложится спать прямо там, мешая проходу других коров с обоих сторон.
  • Если же корова встречает на пути другую спящую корову или достигает конца ряда травы, она расстраивается. Фермер Джон ни при каких условиях не хочет расстраивать своих коров.

Заметим, что трава не отрастает обратно. Также, чтобы не расстраивать корову, Фермер Джон может просто не выбрать каких-то коров.

Удивительно, но Фермер Джон решил, что спящие коровы — наиболее удовлетворенные. Если Фермер Джон будет выбирать порядок оптимально, то какое наибольшее количество спящих коров он сможет получить, и сколько способов существует выбрать два подмножества так, чтобы получить данное максимальное количество спящих коров (по модулю $$$10^9+7$$$)? Порядок, в котором Фермер Джон посылает коров кормиться не важен пока ни одна корова не расстроена.

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

В первой строке задано два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5000$$$, $$$1 \le m \le 5000$$$)  — количество единиц травы в ряду и количество коров.

Во второй строке задано $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le n$$$)  — уровни сладости травы.

В $$$i$$$-й из следующих $$$m$$$ строк задано два целых числа $$$f_i$$$ и $$$h_i$$$ ($$$1 \le f_i, h_i \le n$$$)  — любимый уровень сладости и уровень голода $$$i$$$-й коровы. Никакие две коровы не имеют одинаковый любимый уровень сладости и уровень голода одновременно.

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

Выведите два числа  — максимальное количество спящих коров и количество способов его получить по модулю $$$10^9+7$$$.

Примеры
Входные данные
5 2
1 1 1 1 1
1 2
1 3
Выходные данные
2 2
Входные данные
5 2
1 1 1 1 1
1 2
1 4
Выходные данные
1 4
Входные данные
3 2
2 3 2
3 1
2 1
Выходные данные
2 4
Входные данные
5 1
1 1 1 1 1
2 5
Выходные данные
0 1
Примечание

В первом примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге $$$2$$$ спящих коров:

  • Корова $$$1$$$ стоит с левой стороны и корова $$$2$$$ стоит справа.
  • Корова $$$2$$$ стоит с левой стороны и корова $$$1$$$ стоит справа.

Во втором примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге $$$1$$$ спящую корову:

  • Корова $$$1$$$ стоит слева.
  • Корова $$$2$$$ стоит слева.
  • Корова $$$1$$$ стоит справа.
  • Корова $$$2$$$ стоит справа.

В третьем примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге $$$2$$$ спящих коров:

  • Коровы $$$1$$$ и $$$2$$$ стоят слева.
  • Коровы $$$1$$$ и $$$2$$$ стоят справа.
  • Корова $$$1$$$ стоит слева и корова $$$2$$$ стоит справа.
  • Корова $$$1$$$ стоит справа и корова $$$2$$$ стоит слева.

В четвертом примере, Фермер Джон не может получить ни одной спящей коровы, а потому не будет ни одной коровы стоящей с какой-либо стороны.