AT_joisc2009_sequence 数列 (Sequence)

有一个数列 $a$。给出其前 $m$ 项的值（$a_1$ 到 $a_m$），当 $i\ge m+1$ 时，$a_i=a_{i-1}+a_{i-m}$。给定整数 $p,q$，求 $[p,q]$ 区间内有多少个奇数。

第一行输入一个整数 $m$。 第二行输入一个整数 $p$。 第三行输入一个整数 $q$。 第四行到第 $(m+3)$ 行，第 $(i+3)$ 行输入一个整数 $a_i$。

一行一个整数，即给定范围内奇数的个数。 ### 输入输出样例 #### 输入 #1 ``` 4 2 8 1 2 3 4 ``` #### 输出 #1 ``` 3 ``` #### 输入 #2 ``` 3 1 100 0 0 0 ``` #### 输出 #2 ``` 0 ```

#### 数据规模与约定 - 若你答对了 $q\le 10^6$ 的部分，你将拿到 $60\%$ 的分数。 - 对于全部测试点，保证 $2\le m\le 24$，$0\le a_i\le 2\times 10^9$，$1\le p\lt q\le 2^{60}$。