AT_oupc2023_day1_l KowerKoint Doko

KowerKoint 君がどこかに行ってしまいました。 $ (x, y) $ 座標系において、KowerKoint 君は時刻 $ 0 $ 秒のとき原点 $ (0, 0) $ にいたことがわかっています。KowerKoint 君は、 $ 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

入力は以下の形式で標準入力から与えられます。 > $ T $

$ X $ , $ Y $ をそれぞれ $ \bmod $ $ 998244353 $ で、この順に空白区切りで $ 1 $ 行で出力してください。

### 小課題 1. ( $ 1 $ 点) $ T \leq 1000000 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 2 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 1 \leq T \leq 10^{18} $ - 入力はすべて整数