AT_arc015_4.[ARC015D] きんいろクッキー

高桥君的工作是在一座饼干工厂里，专门点击金色饼干。这个工厂具有以下特点：

• 每秒钟会产生普通饼干和金色饼干，生产的时间是整数秒。
• 正常情况下，每秒会生成 1 块普通饼干。
• 每秒还可能以概率 $P$ 生成 1 块金色饼干。
• 当金色饼干被点击时，它会消失，并触发一种随机效果。
• 共有 $N$ 种效果可以随机触发。对于每种效果 $i$，其出现概率为 $q_i$。当效果触发时，会在之后的 $t_i$ 秒内，使正常生成的饼干数量增加 $x_i$ 倍。
• 效果可以叠加。例如，若在同一秒内，效果 $i$ 出现了两次，效果 $j$ 出现了一次，则该秒生成饼干的总数为 $x_i^2 \times 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

• 第一行包含三个整数：生成饼干的总时间 $T\ (1 \le T \le 100,000)$，效果的种类数 $N\ (1 \le N \le 10,000)$，以及金色饼干出现的概率 $P\ (0 \le P \le 1)$。

• 接下来的 $N$ 行描述每种效果：

  • $q_i$: 效果 $i$ 的出现概率 $(0 \le q_i \le 1)$
  • $x_i$: 效果的倍率 $(1 \le x_i \le 1,000)$
  • $t_i$: 效果的持续时间 $(1 \le t_i \le 100,000)$。

• 所有 $q_i$ 的总和为 $1$。

输出在第 $T-1$ 秒结束后所生成普通饼干总数的期望值。结果精确到小数点后至少三位，并确保绝对误差或相对误差不超过 $10^{-3}$。

• $1 \le T \le 100,000$
• $1 \le N \le 10,000$
• $0 \le P \le 1$
• $\sum_{i=1}^{N} q_i = 1$
• 所有输入的小数精度不超过小数点后第六位
• 正确输出不会超过 $10^{100}$

本翻译由 AI 自动生成