Фишку поставили на поле с системой координат в точку (0, 0).
Каждую секунду фишка перемещается случайным образом. Пусть в некоторый момент времени фишка находится на позиции (x, y). Тогда через секунду она с вероятностью p1 окажется на позиции (x - 1, y), с вероятностью p2 окажется на позиции (x, y - 1), с вероятностью p3 окажется на позиции (x + 1, y), а с вероятностью p4 — на позиции (x, y + 1). Гарантируется, что p1 + p2 + p3 + p4 = 1.
Требуется посчитать математическое ожидание времени, через которое фишка впервые отдалится от начала координат на расстояние, большее R (то есть будет выполнено 
).
Выходные данные
Можно показать, что ответом на задачу всегда является рациональное число вида 
, где 
.
В качестве ответа выведите P·Q - 1 по модулю 109 + 7.
Примечание
В первом тестовом примере фишка изначально находится на расстоянии 0 от начала координат. Через секунду фишка сдвинется на 1 в какую-то сторону, поэтому расстояние от нее до начала координат станет равным 1.
Ответы на второй и третий тесты: 
и 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0 1 1 1 1
|
1
|
|
2
|
1 1 1 1 1
|
666666674
|
|
3
|
1 1 2 1 2
|
538461545
|