После удачного года по количеству удоя, Фермер Джон решил наградить своих коров их любимым угощением: вкусной травой!
На поле располагается ряд из \(n\) единиц травы, каждая единица соответствующего уровня сладости \(s_i\). У Фермера Джона \(m\) коров, каждая обладает своим любимым уровнем сладости \(f_i\) и уровнем голода \(h_i\). Фермер Джон хочет выбрать непересекающиеся подмножества коров, чтобы разместить их с левой и правой стороны ряда травы. Нет никаких ограничений на количество коров с каждой стороны. Поведение коров описывается следующим образом:
- Коровы с левой и правой сторон начинают кормиться по очереди в порядке, выбранном Фермером Джоном.
- Кормежка коровы выглядит следующим образом: корова начинает двигаться к противоположному концу ряда, не меняя своего направления, и поедает траву своего любимого уровня сладости, пока не съест \(h_i\) единиц.
- В тот момент, как корова съест \(h_i\) травы, она ложится спать прямо там, мешая проходу других коров с обоих сторон.
- Если же корова встречает на пути другую спящую корову или достигает конца ряда травы, она расстраивается. Фермер Джон ни при каких условиях не хочет расстраивать своих коров.
Заметим, что трава не отрастает обратно. Также, чтобы не расстраивать корову, Фермер Джон может просто не выбрать каких-то коров.
Удивительно, но Фермер Джон решил, что спящие коровы — наиболее удовлетворенные. Если Фермер Джон будет выбирать порядок оптимально, то какое наибольшее количество спящих коров он сможет получить, и сколько способов существует выбрать два подмножества так, чтобы получить данное максимальное количество спящих коров (по модулю \(10^9+7\))? Порядок, в котором Фермер Джон посылает коров кормиться не важен пока ни одна корова не расстроена.
Выходные данные
Выведите два числа — максимальное количество спящих коров и количество способов его получить по модулю \(10^9+7\).
Примечание
В первом примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге \(2\) спящих коров:
- Корова \(1\) стоит с левой стороны и корова \(2\) стоит справа.
- Корова \(2\) стоит с левой стороны и корова \(1\) стоит справа.
Во втором примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге \(1\) спящую корову:
- Корова \(1\) стоит слева.
- Корова \(2\) стоит слева.
- Корова \(1\) стоит справа.
- Корова \(2\) стоит справа.
В третьем примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге \(2\) спящих коров:
- Коровы \(1\) и \(2\) стоят слева.
- Коровы \(1\) и \(2\) стоят справа.
- Корова \(1\) стоит слева и корова \(2\) стоит справа.
- Корова \(1\) стоит справа и корова \(2\) стоит слева.
В четвертом примере, Фермер Джон не может получить ни одной спящей коровы, а потому не будет ни одной коровы стоящей с какой-либо стороны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 1 1 1 1
1 2
1 3
|
2 2
|
|
2
|
5 2
1 1 1 1 1
1 2
1 4
|
1 4
|
|
3
|
3 2
2 3 2
3 1
2 1
|
2 4
|
|
4
|
5 1
1 1 1 1 1
2 5
|
0 1
|