Наконец-то в городе открылось заведение, предназначенное специально для тех, кто любит кино и не любит компанию. Добро пожаловать в кинотеатр для мизантропов!
Чтобы ничьи головы не заслоняли зрителям экран, кресла в кинотеатре расположены в один ряд и пронумерованы слева направо числами от 1 до N. Перед сеансом посетители заходят в зрительный зал по очереди, и каждый из них может выбрать любое свободное место по своему вкусу.
Разумеется, публика кинотеатра полностью оправдывает его название, поэтому каждый зритель, начиная со второго, будет выбирать себе место таким образом, чтобы оказаться как можно дальше от ближайшего соседа. Если подходящих мест несколько, зритель выберет кресло с наименьшим номером.
Вы знаете, сколько зрителей пришло на сеанс, и какое место выбрал первый из них. Сможете ли вы определить, какое место в итоге займёт каждый зритель?
Ввод содержит целые числа N, M и S1 (1 ≤ N ≤ 106, 1 ≤ M, S1 ≤ N) — соответственно количество мест в кинотеатре, количество зрителей и номер места, которое занял первый зритель.
Вычислите сумму 
(где Si — номер места, занятого i-м зрителем) и выведите остаток от деления этой суммы на 1000000007.
10 7 3
125
40 20 20
3421
В первом примере зрители занимают следующие места: #3, #10, #6, #1, #8, #2, #4.
