問題文

高橋くんのお仕事は、クッキー工場で金色のクッキーをクリックするだけの簡単なお仕事である。
クッキー工場は次の性質を持っている。

• 通常のクッキーと金色のクッキーが生成される。生成される時刻は整数秒である。
• 通常のクッキーは $1$ 秒につき $1$ 枚だけ生成される。
• 金色のクッキーは、通常のクッキーの生成条件とは別に $1$ 秒につき確率 $P$ で $1$ 枚だけ出現する。
• クリックされた金色のクッキーは消滅し、$N$ 通りの効果のうち $1$ 個の効果をもたらす。
• 効果 $i$ は確率 $q_i$ で起こり、その次の秒に生成される通常のクッキーから $t_i$ 回、生成される通常のクッキーの個数を $x_i$ 倍する。
• 上記の効果は重複する。たとえば、ある秒で効果 $i$ が $2$ 回、効果 $j$ が $1$ 回継続している場合、その秒でのクッキーの生成数は $x_i^2\*x_j$ 個となる。

たとえば、開始 $0$ 秒後にクリックした金色のクッキーが持続時間 $3$ 秒、倍率 $2$ 倍の効果を発動し、$1$ 秒後にクリックした金色のクッキーが持続時間 $1$ 秒、倍率 $3$ 倍の効果を発動したとき、生成される通常のクッキーの枚数は、

秒

$0$

$1$

$2$

$3$

$4$

$5$

枚数

$1$

$2$

$6$

$2$

$1$

$1$

となる。
高橋君は皮算用が好きである。$0$ 秒からはじめて、出現する金色のクッキーをすべて出現時にクリックした場合、
$T-1$ 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を求めよ。

---

入力

入力は以下の形式で標準入力から与えられる。$T$ $N$ $P$ $q_1$ $x_1$ $t_1$ $q_2$ $x_2$ $t_2$ : $q_N$ $x_N$ $t_N$

1. $1$ 行目は、クッキーを生成する時間を表す整数 $T\\ (1≦T≦100,000)$、クッキーが持つ効果の種類を表す整数 $N\\ (1≦N≦10,000)$、金色のクッキーが出現する確率 $P\\ (0≦P≦1)$ が半角空白区切りで与えられる。
2. $2$ 行目から $N$ 行は、金色のクッキーをクリックすることで起こる $i$ 番目の効果を表す。その効果が表れる確率 $q_i\\ (0≦q_i≦1)$、その効果の倍率を表す整数 $x_i\\ (1≦x_i≦1,000)$、その効果の持続時間を表す整数 $t_i\\ (1≦t_i≦100,000)$ が、スペース区切りで与えられる。

• $q_i$ の和は $1$ となる。

4. 正しい出力が $10^{100}$ を上回ることはない。
5. 与えられる小数の入力は全て、多くても小数第 $6$ 位までしか存在しない。

出力

$T-1$ 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を1行で出力せよ。
なお、出力の最後には改行をいれること。
出力は絶対誤差あるいは相対誤差の少なくとも片方が $10^{-3}$ 以下であれば許容される。

---

入力例 1

10 2 0.5
0.5 10 1
0.5 2 1

出力例 1

32.5

• 最初の $1$ 秒は、必ず $1$ 枚のクッキーが生成されます。
• $2$ 秒目からは、$10$ 枚のクッキーが生成される確率が $25$、$2$ 枚のクッキーが生成される確率が$25$なので、平均して毎秒 $3.5$ 枚のクッキーが生成されます。

---

入力例 2

100000 3 0.01
0.48175 7 77
0.033325 777 13
0.484925 1 100

出力例 2

16540797.4844572

---

入力例 3

300 1 1
1 2 1000

出力例 3

2037035976334490000000000000000000000000000000000000000000000000000000000000000000000000000

• 出力は指数表記にしてはいけません。誤差が許容される点にも注意してください。

---