マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$120$ 点 $/ 400$ 点

問題文

$x\text{-}y$ 平面上に $N$ 個の点，点 $1, 2, \ldots, N$ があり，点 $i \scriptsize \; (1 \leq i \leq N)$ の座標は $(X_i, Y_i)$ です．

はじめ，MojaMoja くんは平面上の座標 $(0,0)$ にいます．

その後，以下の行動をちょうど $K$ 回行います：

• MojaMoja 君が平面上の座標 $(x', y')$ にいるとき，以下の $4$ 座標のうちいずれかに移動する：
  • $(x' - 1, y')$
  • $(x' + 1, y')$
  • $(x', y' - 1)$
  • $(x', y' + 1)$

$K$ 回の行動後，MojaMoja 君がいる座標に点 $i \scriptsize \; (1 \leq i \leq N)$ があるとき，またそのときに限って MojaMoja 君はちょうど $P_i$ の得点を得ます．(行動後の座標にいずれの点もない場合は何も起こりません．)
なお同一の座標に複数の点が重なっているかもしれません．その場合はそれらの点全てにおいて得点を得ます．

MojaMoja 君の行動の仕方としてあり得るものは $4^K$ 通りありますが，それらの行動によって得られる得点の総和を求めてください．
ただし，答えは非常に大きくなる場合があるので，$998244353$ で割ったあまりを出力してください．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N$
• $0 \leq K$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^5$
• $\sum_{\phi} \Phi_{\phi}(K) \leq 10^5$
• $|X_i|, |Y_i| < 2^{30} \scriptsize \; (1 \leq i \leq N)$
• $0 \leq P_i < 2^{30} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数

小課題

$1. \;(280$ 点$)$

• $\Phi \leq 10^3$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 3 \times 10^3$
• $\sum_{\phi} \Phi_{\phi}(K) \leq 3 \times 10^3$

$2. \;(120$ 点$)$

• 追加の制約はない

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを求め，$998244353$ で割ったあまりを出力せよ．

サンプル

1
2 3
1 0 3
1 1 2

27

たとえば 全 $64 (= 4^K)$ 通りの行動の仕方のうち，ちょうど $3(=K)$ 回で 点 $1$ へ至り $3$ 点を得るものとしては以下の $9$ 通りがあります：

• $(0, 0) \to (-1, 0) \to (0, 0) \to (1, 0)$
• $(0, 0) \to (0, -1) \to (0, 0) \to (1, 0)$
• $(0, 0) \to (0, -1) \to (1, -1) \to (1, 0)$
• $(0, 0) \to (0, 1) \to (0, 0) \to (1, 0)$
• $(0, 0) \to (0, 1) \to (1, 1) \to (1, 0)$
• $(0, 0) \to (1, 0) \to (0, 0) \to (1, 0)$
• $(0, 0) \to (1, 0) \to (1, -1) \to (1, 0)$
• $(0, 0) \to (1, 0) \to (1, 1) \to (1, 0)$
• $(0, 0) \to (1, 0) \to (2, 0) \to (1, 0)$

また，どのように $3 (= K)$ 回の移動を行っても，点 $2$ へ至ることはできません．
したがって $3 \times 9 = 27$ が答えです．

3
7 2
0 0 0
2 2 1000
0 0 1
1 1 998244354
0 0 3
1 1 998244353
0 0 5
1 100
50 50 1
2 0
1 0 1
0 0 2

38
198626801
2

小課題 $1$ のジャッジは こちら

• $\Large \red{\bold{注意}}$：システムの都合上，小課題 $2$ のみに提出する場合，上記リンク先の 小課題 $1$ のジャッジに対しても，同じソースコードを提出してください．このジャッジでは $120$ 点のみが与えられます．
• なお，小課題 $1$ のジャッジに含まれるテストケースはすべてこの 小課題 $2$ のジャッジにも含まれていることを保証します．

以下のジャッジは 小課題 $\Huge \bold{2}$ のものです．