K - Rack Up Points!

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

配点： 点 点

平面上に 個の点，点 があり，点 の座標は です．

はじめ，MojaMoja くんは平面上の座標 にいます．

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

• MojaMoja 君が平面上の座標 にいるとき，以下の 座標のうちいずれかに移動する：

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

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

• 入力はすべて整数

点

点

• 追加の制約はない

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

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

1
2 3
1 0 3
1 1 2

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

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

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

以下のジャッジは 小課題 のものです．