Bitlərin döndürülməsi
Nəhayət n = 2^s, burada s ≥ 0 tam ədəddir. Hər bir tam i üçün 0 ilə n-1 arasında a_i dəyərini aşağıdakı kimi təyin edək. b_{s-1}...b_1b_0 olsun ki, i ədədinin ikilik sistemdə yazılışıdır (zərurət olduqda soldan sıfırlarla s uzunluğuna qədər tamamlanmışdır). Bu bitləri tərs ardıcıllıqla yerləşdirək (b_0b_1...b_{s-1}). Onda 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 olduqda, ikilik yazılış 011_2 olacaq, tərs ardıcıllıqda yazılış isə 110_2 olacaq, müvafiq olaraq, əgər s = 3 olarsa, a_3 = 6 olacaq.
Verilmiş s ədədi üçün a_l+a_{l+1}+...+a_r cəmini 1000000007 modulu üzrə tez bir şəkildə hesablayan sorğulara cavab vermək lazımdır.
Giriş verilənləri
Giriş faylının birinci sətirində tam ədəd s (0 ≤ s ≤ 31) 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ütü l, r (0 ≤ l ≤ r < 2^s) verilmişdir.
Çıxış verilənləri
Çıxış faylında müvafiq sorğulara cavab olaraq k ədəd yazın.