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$$$.