小 A 很喜欢吃东西。
小 A 面前有 n 份食物,第 i 份有参数 a_i 和 b_i。小 A 可以按照任意顺序吃掉这 n 份食物。当她吃掉编号为 i 的食物时,她可以选择将自己的体重乘以 a_i 或者将自己的体重加上 b_i。每份食物只能吃恰好一次。
小 A 的初始体重为 1,请求出她吃完 n 份食物后能达到的最大体重。答案可能很大,你只需要输出其对 ({10}^9 + 7) 取模后的结果。
注意:你需要最大化体重并将该最大值对 \bm{({10}^9 + 7)} 取模,而非最大化体重对 \bm{({10}^9 + 7)} 取模的结果。