003 - 山田うどん-大-

時間制限 2 秒 / メモリ制限 128 MB / 得点 100 / x 9 /


TLE
2sec
MLE
128MB
得点
100

問題

さて、今年もうどん早食い大会の季節がやってきました。
この大会では、優勝することで「山田うどん」で一年間好きなだけうどんを食べる権利を得ることができます。
うどんが大好きな山本君としては負けるわけにはいきません。

この大会では、$ 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$
  • 入力は全て整数である。

入出力例

入力例1

3 6 6

出力例1

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 \ $となり条件を満たす。


入力例2

1 3 1

出力例2

0

条件を満たす組がない場合は$ \ 0 \ $を出力してください。


入力例3

1 1000000000 1000000000

出力例3

29