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

Аркадий и Кирилл пришли на выставку редких монет. Все монеты расположены в один ряд и пронумерованы слева направо от 1 до k, причем некоторые монеты лежат вверх аверсом (главной стороной), а некоторые — вверх реверсом (другой стороной).

Аркадий и Кирилл сделали несколько фотографий монет каждый, причем на каждой фотографии изображены верхние стороны нескольких подряд идущих монет. Аркадий интересуется аверсами, поэтому на каждом снимке, который сделал он, есть хотя бы одна монета, лежащая аверсом вверх. Кирилл, наоборот, интересуется реверсами, поэтому на каждом его снимке есть хотя бы одна монета, лежащая вверх реверсом.

Теперь снимки утеряны, и ребята лишь помнят границы отрезков монет, попавших на каждый из снимков. По данной информации о снимках вычислите остаток от деления на 109 + 7 количества способов выбрать для каждой монеты сторону, которой она будет лежать вверх, так, чтобы на каждом снимке Аркадия была бы хотя бы одна монета вверх аверсом, а на каждом снимке Кирилла была хотя бы одна монета вверх реверсом.

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

Первая строка содержит три целых числа k, n и m (1 ≤ k ≤ 109, 0 ≤ n, m ≤ 105) — общее число монет, количество снимков Аркадия и Кирилла, соответственно.

Следующие n строк содержат описания снимков Аркадия, по одному в строке. Каждая из этих строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ k), означающие, что среди монет с l-й по r-ю должна быть хотя бы одна вверх аверсом.

Следующие m строк содержат описания снимков Кирилла, по одному в строке. Каждая из этих строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ k), означающие, что среди монет с l-й по r-ю должна быть хотя бы одна вверх реверсом.

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

Выведите одно целое число — количество способов выбрать для каждой монеты, какой стороной она будет лежать вверх, по модулю 109 + 7 = 1000000007.

Примеры
Входные данные
5 2 2
1 3
3 5
2 2
4 5
Выходные данные
8
Входные данные
5 3 2
1 3
2 2
3 5
2 2
4 5
Выходные данные
0
Входные данные
60 5 7
1 3
50 60
1 60
30 45
20 40
4 5
6 37
5 18
50 55
22 27
25 31
44 45
Выходные данные
732658600
Примечание

В первом примере возможны следующие расположения монет («А» — аверс, «Р» — реверс):

  • АРААР,
  • АРАРА,
  • АРАРР,
  • РРААР,
  • РРАРА,
  • РРАРР,
  • АРРАР,
  • АРРРА.

Во втором примере данная информация противоречива: согласно снимкам, вторая монета должна лежать одновременно аверсом и реверсом вверх, что невозможно. Значит, ответ равен 0.