У вас есть квадратный лист бумаги со стороной длиной $$$1$$$ единица. За одну операцию вы складываете каждый угол квадрата к центру, образуя таким образом еще один квадрат со стороной длины $$$\dfrac{1}{\sqrt{2}}$$$ единицы. Взяв этот квадрат в качестве нового квадрата, вы выполняете операцию снова и повторяете этот процесс в общей сложности $$$N$$$ раз.

Выполнение операций для $$$N = 2$$$.

После выполнения всех операций вы раскрываете бумагу той же стороной, с которой начали, и видите на ней некоторые линии сгиба. Каждая линия сгиба является одной из двух типов, горой или долиной, гора — это когда бумага складывается наружу, а долина — когда бумага складывается внутрь.

Вычислите сумму длин всех линий горных изгибов на бумаге и назовите ее $$$M$$$. Аналогично вычислите сумму длин для линий долин и назовите ее $$$V$$$. Необходимо найти значение $$$\dfrac{M}{V}$$$.

Можно доказать, что это значение можно представить в виде $$$A + B\sqrt{2}$$$, где $$$A$$$ и $$$B$$$ — рациональные числа. Пусть $$$B$$$ будет представлено в виде несократимой дроби $$$\dfrac{p}{q}$$$, ваша задача — напечатать $$$p*inv(q)$$$ по модулю $$$999\,999\,893$$$ (обратите внимание на необычный модуль), где $$$inv(q)$$$ — модуль, обратный к $$$q$$$.