003 - 山田うどん-大-

問題

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

この大会では、$ 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