题目描述
小明有 $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$。