{"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\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":"\u003cp\u003eNastya received a gift on New Year\u0026nbsp;— a magic wardrobe. It is magic because in the end of each month the number of dresses in it doubles (i.e. the number of dresses becomes twice as large as it is in the beginning of the month).\u003c/p\u003e\u003cp\u003eUnfortunately, right after the doubling the wardrobe eats one of the dresses (if any) with the \u003cspan class\u003d\"tex-span\"\u003e50%\u003c/span\u003e probability. It happens every month except the last one in the year. \u003c/p\u003e\u003cp\u003eNastya owns \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e dresses now, so she became interested in the \u003ca href\u003d\"https://en.wikipedia.org/wiki/Expected_value\"\u003eexpected number\u003c/a\u003e of dresses she will have in one year. Nastya lives in Byteland, so the year lasts for \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e + 1\u003c/span\u003e months.\u003c/p\u003e\u003cp\u003eNastya is really busy, so she wants you to solve this problem. You are the programmer, after all. Also, you should find the answer modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e, because it is easy to see that it is always integer.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe only line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ek\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e18\u003c/sup\u003e\u003c/span\u003e), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e is the initial number of dresses and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e + 1\u003c/span\u003e is the number of months in a year in Byteland.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn the only line print a single integer\u0026nbsp;— the expected number of dresses Nastya will own one year later 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 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\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\u003e2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\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 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21\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\u003eIn the first example a year consists on only one month, so the wardrobe does not eat dresses at all.\u003c/p\u003e\u003cp\u003eIn the second example after the first month there are \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e dresses with \u003cspan class\u003d\"tex-span\"\u003e50%\u003c/span\u003e probability and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e dresses with \u003cspan class\u003d\"tex-span\"\u003e50%\u003c/span\u003e probability. Thus, in the end of the year there are \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e dresses with \u003cspan class\u003d\"tex-span\"\u003e50%\u003c/span\u003e probability and \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e dresses with \u003cspan class\u003d\"tex-span\"\u003e50%\u003c/span\u003e probability. This way the answer for this test is \u003cspan class\u003d\"tex-span\"\u003e(6 + 8) / 2 \u003d 7\u003c/span\u003e.\u003c/p\u003e"}}]}