У вас есть квадратный лист бумаги со стороной длиной \(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\).