← 返回题目列表

AtCoder · oupc2023_day1_l

L. KowerKoint 在哪里

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

配点 : 100 点

問題文

KowerKoint 你去了某个地方。

(x, y) 在坐标系中,KowerKoint 是时间 0 原点时秒 我们知道他在 (0, 0) 。你是1 每秒移动一次,如下(移动是瞬时的):

  • 時刻 1 几秒钟内,KowerKoint 你 转至 (0, 1) 。
  • 時刻 2 移动几秒后,移动前的坐标为 (x,y) 作为 (x+1,y),(x,y+1),(x-1,y),(x,y-1) 可以得到第 4 在三个坐标中,1 排除您在几秒钟前移动之前所在的坐标 3 从此以后,等概率 1 选择一个并移至那里。

時刻 T 在您所在位置的第二个动作 KowerKoint 之后。 x 坐标和 y 每个坐标的期望值为 X, Y 。

X, Y 分别 定义 \bmod 998244353 找到它。

期待値 \bmod 998244353 的定义 可以证明,在这个问题中找到的期望值始终是一个有理数。此外,在该问题的约束下,要寻求的期望值可以表示为不可约分数。 当表示为 \frac{y}{x} 时 保证不能被 x 是 在 998244353 整除。这时, 由于只有一个y≡xz \pmod {998244353} 小于 0 \leq z <998244353 ,z 。 须满足

制約

  • 1 \leq T \leq 10^{18}
  • 所有输入均为整数

小課題

  1. (1 点) T \leq 1000000
  2. (99 点)无附加约束 打印第

入力

输入是按以下格式从标准输入给出的。

T

出力

X, Y 分别 定义 \bmod 998244353 按此顺序,用空格分隔。 1 行输出。


入力例 1

1

出力例 1

0 1

这个测试用例满足小课题1的否定。


入力例 2

2

出力例 2

0 332748119

这个测试用例满足小课题1的否定。