{"raw_statement":[{"iden":"statement","content":"Наконец-то в городе открылось заведение, предназначенное специально для тех, кто любит кино и не любит компанию. Добро пожаловать в кинотеатр для мизантропов!\n\nЧтобы ничьи головы не заслоняли зрителям экран, кресла в кинотеатре расположены в один ряд и пронумерованы слева направо числами от 1 до N. Перед сеансом посетители заходят в зрительный зал по очереди, и каждый из них может выбрать любое свободное место по своему вкусу.\n\nРазумеется, публика кинотеатра полностью оправдывает его название, поэтому каждый зритель, начиная со второго, будет выбирать себе место таким образом, чтобы оказаться как можно дальше от ближайшего соседа. Если подходящих мест несколько, зритель выберет кресло с наименьшим номером.\n\nВы знаете, сколько зрителей пришло на сеанс, и какое место выбрал первый из них. Сможете ли вы определить, какое место в итоге займёт каждый зритель?\n\nВвод содержит целые числа N, M и S1 (1 ≤ N ≤ 106, 1 ≤ M, S1 ≤ N) — соответственно количество мест в кинотеатре, количество зрителей и номер места, которое занял первый зритель.\n\nВычислите сумму  (где Si — номер места, занятого i-м зрителем) и выведите остаток от деления этой суммы на 1000000007.\n\nВ первом примере зрители занимают следующие места: #3, #10, #6, #1, #8, #2, #4.\n\n"},{"iden":"входные данные","content":"Ввод содержит целые числа N, M и S1 (1 ≤ N ≤ 106, 1 ≤ M, S1 ≤ N) — соответственно количество мест в кинотеатре, количество зрителей и номер места, которое занял первый зритель."},{"iden":"выходные данные","content":"Вычислите сумму  (где Si — номер места, занятого i-м зрителем) и выведите остаток от деления этой суммы на 1000000007."},{"iden":"примеры","content":"Входные данные10 7 3Выходные данные125Входные данные40 20 20Выходные данные3421"},{"iden":"примечание","content":"В первом примере зрители занимают следующие места: #3, #10, #6, #1, #8, #2, #4."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of seats in a row, labeled $ 1 $ to $ N $.  \nLet $ M \\in \\mathbb{Z}^+ $ be the number of viewers, with $ M \\leq N $.  \nLet $ S_1 \\in \\{1, \\dots, N\\} $ be the seat chosen by the first viewer.\n\nLet $ S_i \\in \\{1, \\dots, N\\} $ be the seat chosen by the $ i $-th viewer ($ i \\geq 2 $), selected to maximize the minimum distance to any occupied seat, with ties broken by choosing the smallest index.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^6 $  \n2. $ 1 \\leq M \\leq N $  \n3. $ 1 \\leq S_1 \\leq N $\n\n**Objective**  \nCompute $ \\sum_{i=1}^M S_i \\mod 1000000007 $.","simple_statement":"You are given N seats in a row, numbered 1 to N. M people enter one by one. The first person sits at seat S1. Each next person chooses the free seat that is farthest from any occupied seat. If there are multiple such seats, pick the smallest-numbered one. Find the sum of all chosen seat numbers, modulo 1000000007.","has_page_source":false}