{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e在一条坐标线上有$$$n + 2$$$个城镇,编号从$$$0$$$到$$$n + 1$$$。第$$$i$$$个城镇位于坐标点$$$i$$$。\u003c/p\u003e\u003cp\u003e你在每个城镇$$$1, 2, \\dots, n$$$建造一个无线电发射塔的概率为$$$\\frac{1}{2}$$$(这些事件是独立的)。之后,你希望将每个塔的信号功率设置为从$$$1$$$到$$$n$$$的整数(信号功率不一定相同,但也不一定不同)。位于城镇$$$i$$$的塔的信号可以传播到每个城镇$$$c$$$,使得$$$|c - i| \u0026lt; p$$$。\u003c/p\u003e\u003cp\u003e建造完塔后,你希望选择信号功率的方式是:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 城镇$$$0$$$和$$$n + 1$$$不会收到任何塔的信号; \u003c/li\u003e\u003cli\u003e 城镇$$$1, 2, \\dots, n$$$每个只会收到\u003cspan class\u003d\"tex-font-style-it\"\u003e恰好\u003c/span\u003e一个无线电发射塔的信号。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e例如,如果$$$n \u003d 5$$$,并且你已经在城镇$$$2$$$、$$$4$$$和$$$5$$$建造了塔,你可以将城镇$$$2$$$的塔信号功率设置为$$$2$$$,城镇$$$4$$$和$$$5$$$的塔信号功率设置为$$$1$$$。这样,城镇$$$0$$$和$$$n + 1$$$不会收到任何塔的信号,城镇$$$1$$$、$$$2$$$和$$$3$$$会收到城镇$$$2$$$的塔信号,城镇$$$4$$$会收到城镇$$$4$$$的塔信号,城镇$$$5$$$会收到城镇$$$5$$$的塔信号。\u003c/p\u003e\u003cp\u003e计算建造完塔后,你能够以满足所有约束条件的方式设置信号功率的概率。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行(也是唯一的一行)包含一个整数$$$n$$$($$$1 \\le n \\le 2 \\cdot 10^5$$$)。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数 —— 可以满足所有约束条件的设置信号功率的概率,取模$$$998244353$$$。\u003c/p\u003e\u003cp\u003e形式上,概率可以表示为一个不可约分数$$$\\frac{x}{y}$$$。你需要输出$$$x \\cdot y^{-1} \\bmod 998244353$$$的值,其中$$$y^{-1}$$$是一个整数,使得$$$y \\cdot y^{-1} \\bmod 998244353 \u003d 1$$$。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e748683265\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e748683265\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e842268673\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e200000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e202370013\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e第一个示例的真实答案是$$$\\frac{1}{4}$$$:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 以概率$$$\\frac{1}{4}$$$,塔分别建造在城镇$$$1$$$和$$$2$$$,因此我们可以将它们的信号功率设置为$$$1$$$。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e第二个示例的真实答案是$$$\\frac{1}{4}$$$:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 以概率$$$\\frac{1}{8}$$$,塔建造在城镇$$$1$$$、$$$2$$$和$$$3$$$,因此我们可以将它们的信号功率设置为$$$1$$$; \u003c/li\u003e\u003cli\u003e 以概率$$$\\frac{1}{8}$$$,只有一个塔建造在城镇$$$2$$$,我们可以将其信号功率设置为$$$2$$$。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e第三个示例的真实答案是$$$\\frac{5}{32}$$$。请注意,即使前面的解释中使用了相同的信号功率设置,实际上并非总是如此。例如,如果$$$n \u003d 5$$$,并且塔建造在城镇$$$2$$$、$$$4$$$和$$$5$$$,你可以将城镇$$$2$$$的塔信号功率设置为$$$2$$$,城镇$$$4$$$和$$$5$$$的塔信号功率设置为$$$1$$$。\u003c/p\u003e"}}]}