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

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

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