Сегодня у Адилбека тест по теории вероятности. К сожалению, к моменту, когда Адилбек пришел в университет, уже сформировалась огромная очередь из других желающих сдать этот же тест. Адилбек оценил, что он сможет приступить к тесту только через $$$T$$$ секунд.

К счастью, Адилбек может провести время ожидания более интересным образом, чем повторение скучных теорем и формул. У него на телефоне есть приложение с $$$n$$$ японскими кроссвордами. Адилбек собрался решать их по одному, в том же порядке, в котором они перечислены в приложении, не пропуская ни одного кроссворда. Для каждого кроссворда известно время $$$t_i$$$, за которое его в среднем может решить эксперт по кроссвордам (время также задано в секундах).

Адилбек — настоящий эксперт по японским кроссвордам, но, к сожалению, ему иногда не везет с выбором стратегии решения. Поэтому решение $$$i$$$-го кроссворда будет занимать у него либо $$$t_i$$$ секунд, либо $$$t_i + 1$$$ секунд равновероятно (с вероятностью $$$\frac{1}{2}$$$ он решает кроссворд ровно за $$$t_i$$$ секунд, а с вероятностью $$$\frac{1}{2}$$$ он потратит дополнительную секунду на решение кроссворда). Все эти события независимы.

Ровно через $$$T$$$ секунд (либо после решения последнего кроссворда, если он успевает их все решить меньше чем за $$$T$$$ секунд) Адилбек закрывает приложение (если он заканчивает какой-то кроссворд в последний момент, то данный кроссворд считается решенным; иначе Адилбек бросает кроссворд не решенным до конца). Он считает, что будет очень интересно и по теме посчитать $$$E$$$ — математическое ожидание количества кроссвордов, которые он успеет полностью решить. Можете ли вы посчитать данное матожидание?

Напомним, что матожидание дискретной случайной величины — это вероятностно-взвешенное среднее всех ее возможных значений. В данной задаче это означает, что матожидание количества решенных кроссвордов может быть посчитано как как $$$E = \sum \limits_{i = 0}^{n} i p_i$$$, где $$$p_i$$$ — вероятность того, что Адилбек решит ровно $$$i$$$ кроссвордов.

Мы можем представить $$$E$$$ как рациональную дробь $$$\frac{P}{Q}$$$ с $$$Q > 0$$$. В качестве ответа выведите $$$P \cdot Q^{-1} \bmod (10^9 + 7)$$$.