{"trustable":true,"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLeha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed to get access to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e computers throughout the town. Incidentally all the computers, which were hacked by Leha, lie on the same straight line, due to the reason that there is the only one straight street in Vičkopolis.\u003c/p\u003e\u003cp\u003eLet\u0027s denote the coordinate system on this street. Besides let\u0027s number all the hacked computers with integers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. So the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th hacked computer is located at the point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Moreover the coordinates of all computers are distinct. \u003c/p\u003e\u003cp\u003eLeha is determined to have a little rest after a hard week. Therefore he is going to invite his friend Noora to a restaurant. However the girl agrees to go on a date with the only one condition: Leha have to solve a simple task.\u003c/p\u003e\u003cp\u003eLeha should calculate a sum of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003ea\u003c/i\u003e)\u003c/span\u003e for all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e is a non-empty subset of the set, that consists of all hacked computers. Formally, let\u0027s denote \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e the set of all integers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. Noora asks the hacker to find value of the expression \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/e6ea81d63ec55555ebb387a64feb6d75?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. Here \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003ea\u003c/i\u003e)\u003c/span\u003e is calculated as the maximum among the distances between all pairs of computers from the set \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e. Formally, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/7fdfb313162df214121b719f3ff94d48?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. Since the required sum can be quite large Noora asks to find it modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThough, Leha is too tired. Consequently he is not able to solve this task. Help the hacker to attend a date.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e denoting the number of hacked computers.\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e)\u003c/span\u003e denoting the coordinates of hacked computers. It is guaranteed that all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are distinct.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer\u0026nbsp;— the required sum modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThere are three non-empty subsets in the first sample test:\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/63e91da992184b01b027296b3a888bdb?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/113da774c9f8beda4e347778a583a1f1?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e and \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/9099778b44309f672a9746a1d77fe536?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. The first and the second subset increase the sum by \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e and the third subset increases the sum by \u003cspan class\u003d\"tex-span\"\u003e7 - 4 \u003d 3\u003c/span\u003e. In total the answer is \u003cspan class\u003d\"tex-span\"\u003e0 + 0 + 3 \u003d 3\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThere are seven non-empty subsets in the second sample test. Among them only the following subsets increase the answer: \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/8e067febadce611a9ebe37a079967c97?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/7c828463c7009a0d9335a7bac46b5b0c?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a3adfe424038141ed32d0de0f8c84c3d?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/0df31fdb31a8cb9a1dfcfde34330cc1c?v\u003d1715010641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. In total the sum is \u003cspan class\u003d\"tex-span\"\u003e(4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) \u003d 9\u003c/span\u003e.\u003c/p\u003e"}}]}