数列 (Sequence)

数列 {An} は，A1 から Am が入力によって与えられ，i = m + 1 のとき，Ai = Ai−1＋ Ai−m を みたす．この数列の第 p 項から第 q 項 {Ap, . . . , Aq} に含まれる奇数の個数を求めよ．

1 行目には m が書かれている．2 行目には p が 書かれている．3 行目には q が書かれている．i + 3 行目（1 ≤ i ≤ m）には Ai に対応する値が 書かれている．

4 行目から 3 + m 行目に書かれている値は非負整数であり，2 000 000 000 = 2 × 109 よりも小 さい．また，2 ≤ m ≤ 24, 1 ≤ p < q ≤ 260 である．p, q の値が 32bit に収まらないことに注意 せよ．

出力は標準出力に行うこと．指定された範囲に含まれる奇数の数を表す整数を出力 せよ．