← 返回题目列表

Codeforces · 1924/C

C. 分形折纸

中文机器翻译题面 查看原题

您有一张边长等于 $$$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$$$ 的模逆。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$N$$$ ($$$1 \leq N \leq 10^9$$$),即您在方纸上执行的操作数。

输出

对于每个测试用例,在新行中打印所需的答案。

示例

输入 #1

3
1
2
3

输出 #1

0
1
714285638

注意

图中的蓝线代表山折线,绿线代表谷折线。

$$$1$$$ 操作后的折痕线 $$$(\dfrac{M}{V} = 0)$$$。$$$2$$$ 操作后的折痕线 $$$(\dfrac{M}{V} = \sqrt{2} - 1)$$$。