{"problem":{"name":"F. Кинотеатр для мизантропов","description":{"content":"Наконец-то в городе открылось заведение, предназначенное специально для тех, кто любит кино и не любит компанию. Добро пожаловать в кинотеатр для мизантропов! Чтобы ничьи головы не заслоняли зрителям","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10096F"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВвод содержит целые числа N, M и S1 (1 ≤ N ≤ 106, 1 ≤ M, S1 ≤ N) — соответственно количество мест в кинотеатре, количество зрителей и номер места, которое занял первый зритель.\n\n## Выходные Данные\n\nВычислите сумму  (где Si — номер места, занятого i-м зрителем) и выведите остаток от деления этой суммы на 1000000007.\n\n## Примеры\n\nВходные данные10 7 3Выходные данные125Входные данные40 20 20Выходные данные3421\n\n## Примечание\n\nВ первом примере зрители занимают следующие места: #3, #10, #6, #1, #8, #2, #4.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10096F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}