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

Она посадила $$$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}$$$.