Сегодня у Адилбека тест по теории вероятности. К сожалению, к моменту, когда Адилбек пришел в университет, уже сформировалась огромная очередь из других желающих сдать этот же тест. Адилбек оценил, что он сможет приступить к тесту только через \(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)\).