Аркадий и Кирилл пришли на выставку редких монет. Все монеты расположены в один ряд и пронумерованы слева направо от 1 до k, причем некоторые монеты лежат вверх аверсом (главной стороной), а некоторые — вверх реверсом (другой стороной).
Аркадий и Кирилл сделали несколько фотографий монет каждый, причем на каждой фотографии изображены верхние стороны нескольких подряд идущих монет. Аркадий интересуется аверсами, поэтому на каждом снимке, который сделал он, есть хотя бы одна монета, лежащая аверсом вверх. Кирилл, наоборот, интересуется реверсами, поэтому на каждом его снимке есть хотя бы одна монета, лежащая вверх реверсом.
Теперь снимки утеряны, и ребята лишь помнят границы отрезков монет, попавших на каждый из снимков. По данной информации о снимках вычислите остаток от деления на 109 + 7 количества способов выбрать для каждой монеты сторону, которой она будет лежать вверх, так, чтобы на каждом снимке Аркадия была бы хотя бы одна монета вверх аверсом, а на каждом снимке Кирилла была хотя бы одна монета вверх реверсом.
Выходные данные
Выведите одно целое число — количество способов выбрать для каждой монеты, какой стороной она будет лежать вверх, по модулю 109 + 7 = 1000000007.
Примечание
В первом примере возможны следующие расположения монет («А» — аверс, «Р» — реверс):
- АРААР,
- АРАРА,
- АРАРР,
- РРААР,
- РРАРА,
- РРАРР,
- АРРАР,
- АРРРА.
Во втором примере данная информация противоречива: согласно снимкам, вторая монета должна лежать одновременно аверсом и реверсом вверх, что невозможно. Значит, ответ равен 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 2
1 3
3 5
2 2
4 5
|
8
|
|
2
|
5 3 2
1 3
2 2
3 5
2 2
4 5
|
0
|
|
3
|
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
|