Sequence(数列) - joi2009-day1

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

数列{A[n]}は, A[ 1 ]からA[m]が入力によって与えられ, i ≥ m+1 のとき, A[i] = A[i-1] + A[i-m] をみたす. この数列の第p項から第q項 {A[p], …, A[q]} に含まれる奇数の個数を求めよ.

Input.

入力ファイルはsequence.inである. 1行目にはmが書かれている. 2行目にはpが書かれている. 3行目にはqが書かれている. i+3行目 (1 ≤ i ≤ m) にはA[i]に対応する値が書かれている.

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

Output.

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

採点基準

採点用データのうち, 配点の 30% 分は q ≤ 1 000 000 = 10^6 を満たす.

例1

sequence.in	標準出力
4 2 8 1 2 3 4	3

例2

sequence.in	標準出力
3 1 100 0 0 0	0