問題
さて、今年もうどん早食い大会の季節がやってきました。
この大会では、優勝することで「山田うどん」で一年間好きなだけうどんを食べる権利を得ることができます。
うどんが大好きな山本君としては負けるわけにはいきません。
この大会では、$ L \ $以上$ \ R \ $以下の整数の中から二つの整数$ \ l, r \ (l \lt r) \ $を選ぶと、味の濃さが$ \ l,l+1,\ldots,r \ $であるようなうどんが計$ \ r - l + 1 \ $杯この順番に並べられます。
そこで山本君は、速く食べることができ、かつ飽きの来ない食べ方として、以下のような食べ方を考え出しました。
- $ \ r - l + 1 \ $杯のうどんを残り$ \ 1 \ $杯になるまで次のようにうどんを食べ、最後に$ \ 1 \ $つだけ残ったうどんを味わって食べる。
- 食べ終わっていないうどんのうち、先頭から奇数番目のうどんを全て食べる。
山本君は味の濃さが$ \ K \ $であるようなうどんが大好きなので、この味の濃さのうどんを最後に味わって食べたいです。
そんな山本君のために、最後に味わって食べるうどんの味の濃さが$ \ K \ $であるような整数$ \ l,r \ (L \leq l \lt r \leq R) \ $の組の個数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$L \ R \ K$
出力
条件を満たすような$ \ l, r \ $の組の個数を出力せよ。出力の末尾には改行を入れること。
制約
- $1 \leq L \lt R \leq 10^9$
- $L \leq K \leq R$
- 入力は全て整数である。
入出力例
入力例１
3 6 6
出力例１
2
$A \ $を並べられているうどんとする。
$(l,r) = (3,6),(5,6) \ $すなわち、$A = (3,4,5,6),(5,6) \ $であるとき条件を満たす。
例として、$A = (3,4,5,6) \ $の場合以下のようになる。
- $1 \ $回目で$ \ 3,5 \ $のうどんを食べ、$A = (4,6) \ $となる。
- $2 \ $回目で$ \ 4 \ $のうどんを食べ、$A = (6) \ $となる。
よって、最後に残るのは$ \ 6 \ $となり条件を満たす。
入力例２
1 3 1
出力例２
0
条件を満たす組がない場合は$ \ 0 \ $を出力してください。
入力例３
1 1000000000 1000000000
出力例３
29