{"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\u003eToday Adilbek is taking his probability theory test. Unfortunately, when Adilbek arrived at the university, there had already been a long queue of students wanting to take the same test. Adilbek has estimated that he will be able to start the test only $$$T$$$ seconds after coming. \u003c/p\u003e\u003cp\u003eFortunately, Adilbek can spend time without revising any boring theorems or formulas. He has an app on this smartphone which contains $$$n$$$ Japanese crosswords to solve. Adilbek has decided to solve them all one by one in the order they are listed in the app, without skipping any crossword. For each crossword, a number $$$t_i$$$ is given that represents the time it takes an average crossword expert to solve this crossword (the time is given in seconds).\u003c/p\u003e\u003cp\u003eAdilbek is a true crossword expert, but, unfortunately, he is sometimes unlucky in choosing the way to solve the crossword. So, it takes him either $$$t_i$$$ seconds or $$$t_i + 1$$$ seconds to solve the $$$i$$$-th crossword, equiprobably (with probability $$$\\frac{1}{2}$$$ he solves the crossword in exactly $$$t_i$$$ seconds, and with probability $$$\\frac{1}{2}$$$ he has to spend an additional second to finish the crossword). All these events are independent.\u003c/p\u003e\u003cp\u003eAfter $$$T$$$ seconds pass (or after solving the last crossword, if he manages to do it in less than $$$T$$$ seconds), Adilbek closes the app (if he finishes some crossword at the same moment, that crossword is considered solved; otherwise Adilbek does not finish solving the current crossword at all). He thinks it would be an interesting probability theory problem to calculate $$$E$$$ — the expected number of crosswords he will be able to solve completely. Can you calculate it? \u003c/p\u003e\u003cp\u003eRecall that the expected value of a discrete random variable is the probability-weighted average of all possible values — in this problem it means that the expected value of the number of solved crosswords can be calculated as $$$E \u003d \\sum \\limits_{i \u003d 0}^{n} i p_i$$$, where $$$p_i$$$ is the probability that Adilbek will solve exactly $$$i$$$ crosswords. \u003c/p\u003e\u003cp\u003eWe can represent $$$E$$$ as rational fraction $$$\\frac{P}{Q}$$$ with $$$Q \u0026gt; 0$$$. To give the answer, you should print $$$P \\cdot Q^{-1} \\bmod (10^9 + 7)$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$T$$$ ($$$1 \\le n \\le 2 \\cdot 10^5$$$, $$$1 \\le T \\le 2 \\cdot 10^{14}$$$) — the number of crosswords and the time Adilbek has to spend, respectively.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers $$$t_1, t_2, \\dots, t_n$$$ ($$$1 \\le t_i \\le 10^9$$$), where $$$t_i$$$ is the time it takes a crossword expert to solve the $$$i$$$-th crossword.\u003c/p\u003e\u003cp\u003eNote that Adilbek solves the crosswords in the order they are given in the input without skipping any of them.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint one integer — the expected value of the number of crosswords Adilbek solves in $$$T$$$ seconds, expressed in the form of $$$P \\cdot Q^{-1} \\bmod (10^9 + 7)$$$.\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\u003e3 5\n2 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e750000007\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 5\n2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e125000003\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\u003eThe answer for the first sample is equal to $$$\\frac{14}{8}$$$.\u003c/p\u003e\u003cp\u003eThe answer for the second sample is equal to $$$\\frac{17}{8}$$$.\u003c/p\u003e"}}]}