当前没有测试数据。

2.电影问题

题目描述

小明有$n$部电影，每个电影都有一个时长，以及小明喜欢每部电影的概率。若小明现在已经看完了一部电影，如果小明喜欢这部电影，那么他会增加等同于电影长度的快乐值，并且如果他还没有收藏这部电影，那么他会把这个电影收藏起来；如果小明不喜欢这部电影，那么他会降低等同于电影长度的快乐值，并且会把之前收藏的电影再看一遍，来增加自己的快乐值。小明已经想出了一个看电影的顺序，使得他期望增加的快乐值最大。问小明在这个顺序下期望增加的快乐值对$1004535809$取模的值。

输入格式

第一行一个正整数$n$。

接下来$n$行每行三个正整数$l_i$，$x_i$，$y_i$，其中$l_i$表示电影的长度，$\frac{x_i}{y_i}$表示小明喜欢这部电影的概率。

输出格式

仅一个整数，表示答案。

数据范围与提示

• 对于$20\%$的数据，$n \leq 5$；
• 对于$50\%$的数据，$n \leq 1000$；
• 另有$20\%$的数据，$l_i$全都相等，$x_i$全都相等，$y_i$全都相等；
• 对于$100\%$的数据，$1 \leq n \leq 2 \times 10^{5}$，$1 \leq x_i \leq y_i \leq 10^{6}$，$0 \leq l_i \leq 10^{6}$。

样例

2
1 1 2
2 1 2

502267905