{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \u003cp\u003eВ университете Павлополиса, где учится Нура, решили провести конкурс красоты «Мисс университета Павлополиса». Опишем подробнее процесс выбора самой красивой девушки в университете.\u003c/p\u003e \u003cp\u003eКонкурс проходит в несколько этапов. Пусть изначально в конкурсе участвует \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e девушек. Всех участниц делят на \u003cspan class\u003d\"tex-font-style-bf\"\u003eравные\u003c/span\u003e группы по \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e человек в каждой. При этом число \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e выбирается произвольно, то есть число \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e может быть различным для разных этапов конкурса. Внутри каждой группы жюри конкурса сравнивает девушек по красоте в формате «каждая с каждой». Таким образом, если в группе \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e девушек, то происходит \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://espresso.codeforces.com/90eda7186d150a31a8a1f356c79097a0591eb8c0.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e сравнений. Затем из каждой группы выбирается по одной самой красивой участнице. Выбранные девушки попадают в следующий этап конкурса. То есть, если \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e девушек были разделены на группы, по \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e участниц в каждой, то в следующий этап попадут ровно \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://espresso.codeforces.com/73ee00e56876de3fc3efc21fb6d81038dff5ed20.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e участниц. Конкурс продолжается до тех пор, пока не останется ровно одна девушка, которая и будет признана «Мисс университета Павлополиса».\u003c/p\u003e \u003cp\u003eНо для жюри этот конкурс\u0026nbsp;— очень утомительное занятие. Им хотелось бы делить девушек на группы в каждом этапе так, чтобы суммарное число попарных сравнений девушек было как можно меньше. Обозначим за \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ef\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e)\u003c/span\u003e минимальное суммарное количество сравнений, которые надо провести, чтобы выбрать самую красивую участницу, если к первому этапу допустить \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e девушек.\u003c/p\u003e \u003cp\u003eОрганизаторы конкурса — большие сумасброды. Они дают Нуре три целых числа \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003et\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003el\u003c/i\u003e\u003c/span\u003e и \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003er\u003c/i\u003e\u003c/span\u003e и просят бедную девушку посчитать значение следующего выражения: \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003et\u003c/i\u003e \u003csup class\u003d\"upper-index\"\u003e0\u003c/sup\u003e·\u003ci\u003ef\u003c/i\u003e(\u003ci\u003el\u003c/i\u003e) + \u003ci\u003et\u003c/i\u003e \u003csup class\u003d\"upper-index\"\u003e1\u003c/sup\u003e·\u003ci\u003ef\u003c/i\u003e(\u003ci\u003el\u003c/i\u003e + 1) + ... + \u003ci\u003et\u003c/i\u003e \u003csup class\u003d\"upper-index\"\u003e \u003ci\u003er\u003c/i\u003e - \u003ci\u003el\u003c/i\u003e\u003c/sup\u003e·\u003ci\u003ef\u003c/i\u003e(\u003ci\u003er\u003c/i\u003e)\u003c/span\u003e. Однако, так как значение этого выражения может быть достаточно велико, организаторы просят посчитать его по модулю \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e. Если Нура сможет посчитать значение этого выражения, организаторы обещают ей помощь в ходе конкурса красоты. Но бедная девушка не сильна в математике, поэтому за помощью она обратилась к Лехе, а тот — прямиком к вам.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eВ первой и единственной строке задано три целых числа \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003et\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003el\u003c/i\u003e\u003c/span\u003e и \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003er\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e \u0026lt; 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7, 2 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"output-specification\"\u003e \u003cdiv class\u003d\"section-title\"\u003eВыходные данные\u003c/div\u003e \u003cp\u003eВыведите единственное число — значение искомого выражения по модулю \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e2 2 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e19\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cdiv class\u003d\"note\"\u003e \u003cdiv class\u003d\"section-title\"\u003eПримечание\u003c/div\u003e \u003cp\u003eРассмотрим пример.\u003c/p\u003e \u003cp\u003eНеобходимо найти значение \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://espresso.codeforces.com/3ecc798906ae9e9852061ba2dd5cf6b8fce7753b.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e.\u003c/p\u003e \u003cp\u003e \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ef\u003c/i\u003e(2) \u003d 1\u003c/span\u003e. Из двух девушек можно составить только одну группу из двух человек, в которой произойдет одно сравнение.\u003c/p\u003e \u003cp\u003e \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ef\u003c/i\u003e(3) \u003d 3\u003c/span\u003e. Из трех девушек можно составить только одну группу из трех человек, в которой произойдет три сравнения.\u003c/p\u003e \u003cp\u003e \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ef\u003c/i\u003e(4) \u003d 3\u003c/span\u003e. Четырех девушек можно разбить на две группы по две девушки в каждой. Тогда на первом этапе произойдет два сравнения, по одному в каждой из двух групп. Во второй этап выйдут две девушки, между которыми произойдёт ещё одно сравнение. Итого \u003cspan class\u003d\"tex-span\"\u003e2 + 1 \u003d 3\u003c/span\u003e. Можно также в первом этапе оставить всех девушек в одной группе. Тогда произойдет \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://espresso.codeforces.com/fcc6c9e72a1525cc01abbfb89094669a9d37d3b1.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e сравнений. Очевидно, что лучше разбивать девушек на группы первым способом.\u003c/p\u003e \u003cp\u003eТогда значение выражения это \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://espresso.codeforces.com/2c5a0f75c9d910ec77b2fe675e690de453060631.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e.\u003c/p\u003e\u003c/div\u003e"}}]}