Задача . E. Эла идет в поход

Эла любит ходить в походы. Она любит природу и исследует различных животных. Однажды она увидела муравьев странного вида с каннибальскими наклонностями. В частности, муравей такого вида съест любого меньшего муравья, которого он увидит. Заинтересовавшись этой особенностью, Эла решила провести эксперимент.

Она посадила \(n\) муравьев-каннибалов в ряд на длинной деревянной палке. Изначально все муравьи имеют одинаковый вес \(1\). Расстояние между любыми двумя соседними муравьями одинаково. Расстояния между первым муравьем в цепочке до левого конца палки и последним муравьем в цепочке до правого конца палки также одинаковы и равны расстоянию между двумя соседними муравьями. В какой-то момент каждый муравей начинает двигаться влево либо вправо равновероятно случайным образом с одной и той же постоянной для всех муравьев скоростью на протяжении всего эксперимента. Муравьи поворачиваются в обратную сторону сразу же, как только достигнут конца палки. Вскоре Эле удалось выяснить поведение муравьев в случае встречи.

• Если два муравья разного веса встретятся, более тяжелый мгновенно съест более легкого и увеличит свой вес на вес более легкого. После этого он продолжит идти в том же направлении. Например, если более тяжелый муравей имеет вес \(x\) и идет вправо, а более легкий имеет вес \(y\) и идет влево (\(x > y\)), то после встречи более легкий будет съеден, а более тяжелый будет иметь вес \(x + y\) и продолжит идти вправо.
• Если два муравья одного веса встретятся, то тот, кто идет влево, мгновенно съест того, кто идет вправо, а затем продолжит идти в том же направлении. Другими словами, если один муравей веса \(x\), идущий влево, встретится с другим муравьем веса \(x\), идущим вправо, то муравей, идущий вправо, будет съеден, а идущий влево будет весить \(2x\) и продолжит двигаться влево.

Заметьте, что два муравья могут встретиться, только если идут в разные стороны

Можно доказать, что через определенное время останется только один муравей. Изначально каждый муравей будет случайным образом равновероятно двигаться влево или вправо, что порождает \(2^n\) различных случаев начального движения. Для каждого муравья вычислите вероятность того, что он в итоге выживет. Выведите ее по модулю \(10^9 + 7\).

Формально, пусть \(M = 10^9 + 7\). Можно показать, что ответ можно представить в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, а \(q \not \equiv 0 \pmod{M}\). Выведите целое число, равное \(p \cdot q^{-1} \bmod M\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p \pmod{M}\).