JATC любит Бань-ми (вьетнамское блюдо). Его привязанность к Бань-ми настолько велика, что он ест Бань-ми каждый день на завтрак. Сегодня утром, как обычно, он купил Бань-ми, но собирается насладиться им необычным образом.
Сначала, он разбивает Бань-ми на \(n\) кусочков, выкладывает их в ряд и нумерует от \(1\) до \(n\). Для каждого кусочка \(i\) он определяет его вкусность как \(x_i \in \{0, 1\}\). JATC собирается съесть все кусочки один за другим. Каждый раз он выбирает произвольный из оставшихся кусочков и съедает его. Пусть этот кусочек был под номером \(i\), тогда его удовольствие от Бань-ми увеличивается на \(x_i\), вкусность каждого из оставшихся кусочков также увеличивается на \(x_i\). Изначально удовольствие JATC равно \(0\).
Например, пусть есть \(3\) кусочка с вкусностями \([0, 1, 0]\). Если JATC съест второй кусочек, то его удовольствие станет равно \(1\), а вкусность оставшихся кусочков будет равна \([1, \_, 1]\). Затем, если он съест первый кусочек, то его удовольствие станет равна \(2\), а вкусность оставшихся кусочков станет \([\_, \_, 2]\). После того как JATC съест последний кусочек, его удовольствие станет равно \(4\).
Однако JATC не хочет съесть сразу все кусочки, оставив часть на будущее. Он дал вам \(q\) запросов, каждый из которых задаётся двумя целыми числам \(l_i\) и \(r_i\). Для каждого запроса выясните какое наибольшее удовольствие он может получить, если съест все кусочки в отрезке \([l_i, r_i]\) в каком-то порядке.
Все запросы независимы друг от друга. Так как ответ на запрос может быть очень большим, выведите его по модулю \(10^9+7\).