004 - 鉄道旅行 (Rail Travel)

時間制限 8 秒 / メモリ制限 256 MB / 得点 100 / x 0 /

TLE
8sec
MLE
256MB
得点
100

問題

冬休みの時期になった. ミズゴロウのゴロウくんは, この休みのうちに電車に乗って旅行をしようと考えた.

ゴロウくんは JOI 鉄道の IOI 線に乗って旅をする. IOI 線には N 個の停車駅がある. それぞれの駅には 1 から N までの番号がついていて, 駅 i (2 ≤ i ≤ N - 1) は, 駅 i - 1 および駅 i + 1 と隣接している. また, これら N 個の駅の間を, M 本の電車が行き来する.

i (1 ≤ i ≤ M) 番目の電車は, 時刻 Ai に駅 Bi を出発し, 駅 Bi + Ci, 駅 Bi + 2Ci, ... の順に停車する. どの電車も, 駅 i と駅 i + 1 の間を行き来する間に時刻が 1 増える. つまり, 電車 i が駅 Bi + Ci, 駅 Bi + 2Ci, ... に停車する時刻はそれぞれ Ai + |Ci|, Ai + 2|Ci|, ... となる. (|x| は x の絶対値を表す. x ≥ 0 なら |x| = x, x < 0 なら |x| = -x である.) 複数の電車が同じ時刻に 1 つの駅に停車する可能性があることに注意せよ.

ゴロウくんは, 時刻 0 に駅 S にいる. 彼は電車を乗り継いで, 駅 T に行こうと考えている. ゴロウくんには時間がたっぷりあるので, 駅 T にはどの時刻についてもかまわない. また, 一度駅 T についた後, 別の駅に行ってまた駅 T に戻ってきても構わない. この条件をみたすように電車に乗る方法は何通りあるだろうか. 電車の乗り方の総数はとても多くなることがあるため, 乗り方の総数を 100000 で割ったあまりを求めるプログラムを作成せよ.

ここで, ゴロウくんは, 電車の乗換に慣れているので, 時刻 X に駅 Y に停車する電車から, 同時刻に駅 Y を発車する別の電車にすぐに乗り換えることが出来る. つまり, ゴロウくんが電車の乗換をするためにかかる時間は無視することが出来るものとする.

入力

入力は M + 1 行からなる.
1 行目には 4 つの整数 N, M, S, T ( 2 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ S, T ≤ N ) が空白を区切りとして書かれている. S と T は異なる整数であることが保証されている.
1 + i 行目 ( 1 ≤ i ≤ M ) には, i 番目の電車についての情報を表す 3 つの整数 Ai, Bi, Ci (1 ≤ Ai ≤ 100, 1 ≤ Bi ≤ N, 1 ≤ |Ci| ≤ N - 1) が空白を区切りとして書かれている.
ここで, それぞれの電車は出発する駅以外で少なくとも 1 つ別の駅に停車することが保証されている. つまり, 1 ≤ Bi + Ci ≤ N が保証されている.

出力

電車の乗り方の総数を 100000 で割ったあまりを 1 行に出力せよ.

入出力例

入力例 1

5 3 2 4
1 1 1
2 2 2
5 5 -1

出力例 1

4

入力例 1 では, 次の 4 通りの方法で駅 2 から駅 4 に行くことが出来る.

  • 時刻 2 に駅 2 で電車 1 に乗って, 時刻 4 に駅 4 で電車 1 から降りる.
  • 時刻 2 に駅 2 で電車 2 に乗って, 時刻 4 に駅 4 で電車 2 から降りる.
  • 時刻 2 に駅 2 で電車 1 に乗って, 時刻 5 に駅 5 で電車 1 から降り, 電車 3 に乗り換える. 時刻 6 に駅 4 で電車 3 から降りる.
  • 時刻 2 に駅 2 で電車 2 に乗って, 時刻 4 に駅 4 で電車 2 から降り, 電車 1 に乗り換える. 時刻 5 に駅 5 で電車 1 から降り, 電車 3 に乗り換える. 時刻 6 に駅 4 で電車 3 から降りる.

入力例 2

5 2 1 5
1 1 1
1 1 1

出力例 2

16

入力例 2 では, 1 番目の電車と 2 番目の電車が並走している. 駅 i と駅 i + 1 (1 ≦ i ≦ 4) の間で, 乗れる電車が 2 通りずつあるので, 駅 1 から駅 5 へ行くための電車の乗り方の総数は 24 = 16 通りである.

入力例 3

30 13 7 27
1 1 1
40 30 -1
12 1 2
18 6 1
20 7 4
50 29 -2
20 19 -1
10 3 3
2 1 1
31 21 -4
60 1 1
44 30 -3
45 19 -1

出力例 3

92316

入力例 3 の条件を満たす電車の乗り方の総数は 1492316 通りある. 100000 で割ったあまりを出力することに注意せよ.