Bitlərin döndürülməsi 2
Qoy n = 2^s, burada s ≥ 0 tam ədəddir. Hər bir tam i üçün 0-dan n-1-ə qədər a_i dəyərini aşağıdakı kimi təyin edək. Qoy b_{s-1}...b_1b_0 — i ədədinin ikilik say sistemində yazılışı olsun (zərurət olduqda s uzunluğuna qədər soldan sıfırlarla tamamlanmış). Bu bitləri tərsinə düzün (b_0b_1...b_{s-1}). O zaman a_i dəyəri ikilik yazılışı b_0b_1...b_{s-1} olan ədəd olacaq.
Məsələn, s = 3, i = 3, o zaman ikilik yazılış 011_2 olacaq, tərs yazılış isə 110_2, müvafiq olaraq, əgər s = 3, onda a_3 = 6.
Verilmiş s ədədi üçün a_l+a_{l+1}+...+a_r cəmini 1000000007 modulu ilə tez bir zamanda hesablamaq lazımdır.
Giriş verilənləri
Giriş faylının birinci sətirində tam ədəd s (0 ≤ s ≤ 25) yazılmışdır. İkinci sətirdə tam ədəd k — sorğuların sayı (1 ≤ k ≤ 5·10^5) yazılmışdır. Növbəti k sətirdə sorğuların özləri — tam ədədlər cütləri l, r (0 ≤ l ≤ r < 2^s) verilir.
Çıxış verilənləri
Çıxış faylında müvafiq sorğulara cavab olaraq k ədəd yazın.