L - KowerKoint Doko Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

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 <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 の制約を満たします。