小 B 很喜欢吃东西。

小 B 面前有 n 份食物，第 i 份有参数 a i ​ 和 b i ​ 。小 B 可以按照任意顺序吃掉这 n 份食物。

当她吃掉编号为 i 的食物时，她可以选择将自己的体重乘以 a i ​ 或者将自己的体重加上 b i ​ 。每份食物只能吃恰好一次。

小 B 的初始体重为 1，请求出她吃完 n 食物后能达到的最大体重。答案可能很大，你只需要输出其对 (10^9 +7) 取模后的结果。

5 1 2 3 4 5 100 200 300 400 500

18060