F. Кинотеатр для мизантропов

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