Maximizing Little A's Weight

Little A loves food. In front of her, there are \( n \) food items. The \( i\)-th food has two parameters \(a_i\) and \(b_i\). She can eat the foods in any order. When she eats the \( i\)-th food, she may choose either to multiply her current weight by \(a_i\) or to add \(b_i\) to her weight. Each food must be eaten exactly once.

She starts with a weight of \(1\), and her goal is to maximize her final weight. Formally, if she chooses a sequence of operations \(op_1, op_2, \ldots, op_n\) corresponding to a permutation of the foods (with each \(op_i\) being either multiply by \(a_i\) or add \(b_i\)), her final weight \(W\) is computed by applying these operations sequentially starting from \(1\). You need to maximize \(W\) and output its remainder modulo \(10^9+7\).

Note: You need to maximize the actual weight and then take the modulo \(10^9+7\) of the maximum weight, rather than maximizing the weight under modulo \(10^9+7\).

Constraints: \(1 \leq n \leq 15\) and \(1 \leq a_i, b_i \leq 10\).

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 15\)), representing the number of food items.

Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) (\(1 \le a_i, b_i \le 10\)), representing the parameters of the \(i\)-th food.

outputFormat

Output a single integer: the maximum possible weight after eating all food items, taken modulo \(10^9+7\).

sample

1
2 6

14