問題文

あなたは今ジャパリパークという動物園のとある「ちほー」と呼ばれるエリアにいます。
このちほーは東西方向に$H$メートル、南北方向に$W$メートルの$(H+1)*(W+1)$の格子点から構成される升目で表現され、あなたは今$(0,0)$にいます。あなたは東と北のみの移動で$(H,W)$まで行こうとしています。
このちほーの各所にはフレンズと呼ばれるヒトの姿をした動物がおり、それぞれ$N[i]$という名前で$(x[i],y[i])$にいることがわかっています。また、一箇所にいるフレンズは1体以下です。
フレンズのいる所は通ることができませんが、ジャパリまんというおまんじゅうを１つ渡すと通れるようになります。
スタートやゴールにもフレンズがいる場合はありません。
（注：当初いるという想定でしたが、実際のテストケースにはないのと事態を鑑みて、いないものとしました。）

最短で$(H,W)$まで行く経路が最も多くなるようにジャパリまんを渡すフレンズの名前を、また経路の数を$1000000007$で割った余りを出力してください。
但し、$(H,W)$までたどり着けない場合は0を出力すること。全てのテストケースはたどり着けない場合及びジャパリまんを持っていない場合を除き、最大経路となる例は一つである。

入力

$H$ $W$ $K$ $P$
$x[1]$ $y[1]$ $N[1]$
$x[2]$ $y[2]$ $N[2]$
…
$x[K]$ $y[K]$ $N[K]$

$H$はこのちほーの東西方向の長さを表しています。
$W$はこのちほーの南北方向の長さを表しています。
$K$はこのちほーにいるフレンズの数を表しています。
$P$はあなたが持っているジャパリまんの数を表しています。
$x[i]$,$y[i]$は$i$番目のフレンズが$(x[i],y[i])$にいることを表しています。
$N[i]$は$i$番目のフレンズの名前を表しています。
$N[i]$のみ文字列で、その他はすべて整数です。

$1≤H,W≤32$
$1≤K≤min(15,(H+1) \times (W+1) - 2)$
$0≤P≤K$
$0≤x[i]≤H$
$0≤y[i]≤W$
$i≠j$のとき$(x[i],y[i])≠(x[j],y[j])$
($x$、$y$のどちらかのみが一致することはある)
$(x[i],y[i]) \ne (0,0),(H,W)$
（スタートとゴールにはフレンズはいない）
$i≠j$のとき$N[i]≠N[j]$
$N[i]$は半角英字(小文字のみ)で1文字以上10文字以内
たどり着けない場合及びジャパリまんを持っていない場合を除き、最大経路となる例は一つである

出力

1行目に最多となる最短経路の数を$1000000007$で割った余りを出力してください。
続いてジャパリまんをあげるフレンズの名前を入力された順に改行区切りで出力してください。
最後に改行してください。

サンプル

1 2 1 1
0 1 serval

3
serval

3 4 2 0
3 3 konoha
2 4 mimi

0

10 10 6 4
2 9 moose
1 8 chameleon
4 7 shoebill
5 8 porcupine
6 7 whiterhino
6 5 armadillo

183928
shoebill
porcupine
whiterhino
armadillo