Minus K
题号：NC200047
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Cirno (⑨) 具有操纵冷气程度的能力，某一天，Cirno想要改进她的冻符「Minus K」，具体地说，她想要做这样一件事：

Cirno首先会放出1个冰块，这里记作ICE_0。
之后她会控制这个冰块使其分裂，这里将ICE_0分裂产生的冰块记作ICE_1。
之后她可能会再次控制全部的ICE_1使其分裂，使其变成新的冰块，记作ICE_2，以此类推。

形式化地，对于冰块ICE_i，进行分裂后会得到冰块，并且只要Cirno下定决心将某一种冰块分裂，全部此种冰块都会被分裂。
定义一个计数函数cnt(x)，表示冰块x总共产生过多少个。

显然最初的冰块ICE_0只有一个，即。
Cirno会将ICE_0分裂成k_1份ICE_1，所以。
以此类推，Cirno总会将每个ICE_i分裂成份。

Cirno会分裂冰块n次，之后Cirno想知道从ICE_l到ICE_r的每种冰块总共出现了多少次（包含ICE_l和ICE_r），因为结果可能很大，无法使用普通的整型存放下，所以请将结果对20090909取模。

形式化表述为，对于每次询问，输出的值。

输入描述:

输入第一行包含两个正整数n和q，之间使用一个空格符分隔，表示Cirno分裂冰块的次数，以及询问次数。
之后第二行包含n个正整数，相邻正整数之间使用一个空格符分隔，按照输入顺序的第i个正整数记作k_i，表示会将冰块分裂成k_i块冰块ICE_i。
之后连续输入q行，每行一个两个非负整数，之间使用一个空格符分隔，这种输入的第i行的两个整数记作，即题目描述中的每次询问。

数据规范：
* .
* .
* .

输出描述:

输出q行，每行一个正整数，即按照输入顺序依次回答每次询问。
示例1

输入

复制 
2 6
2 3
0 0
1 1
2 2
0 1
1 2
0 2

输出

复制 
1
2
6
3
8
9

说明

备注:

数据量较大，请使用相对快速的输入输出方式。