问题文

高桥君的工作很简单，只需要在饼干工厂里点击金色的饼干。饼干工厂具有以下特性：

• 会生成普通饼干和金色饼干。生成的时间以整数秒为单位。
• 普通饼干每秒钟生成1个。
• 金色饼干除了满足普通饼干的生成条件外，还有独立的概率P在每秒钟生成1个。
• 被点击的金色饼干会消失，并带来N种效果中的1种。
• 效果i以概率qi发生，并使之后生成的普通饼干数量增加ti次，倍率为xi倍。
• 上述效果可以重叠。例如，在某一秒内，效果i连续发生2次，效果j发生1次，则该秒内生成的饼干数量为xi^2*xj个。

例如，在开始0秒后点击的金色饼干持续3秒，触发2倍效果，在1秒后点击的金色饼干持续1秒，触发3倍效果时，生成的普通饼干数量为：

秒

0

1

2

3

4

5

数量

1

2

6

2

1

1

高桥君喜欢做算术题。从0秒开始，如果他在金色饼干出现时都点击一次，求在第T-1秒结束时，生成的普通饼干总数的期望值。

---

输入

从标准输入中以以下格式给出输入：T N P
q1 x1 t1
q2 x2 t2
:
qN xN tN

1. 第1行包含3个整数，以空格分隔：T表示生成饼干的时间（1≤T≤100,000），N表示饼干的效果种类（1≤N≤10,000），P表示金色饼干出现的概率（0≤P≤1）。
2. 接下来的N行分别描述第i种效果：效果i发生的概率qi（0≤qi≤1），效果i增加的倍率xi（1≤xi≤1,000），效果i持续的时间ti（1≤ti≤100,000）。

• 所有qi之和等于1。

4. 输出正确结果不会超过$10^{100}$。
5. 给定的小数输入至多保留小数点后6位。

输出

请在一行中输出第T-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

• 输出不能使用指数表示法。请注意误差的可接受范围。