Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1300 点
問題文
あなたは、RPG ゲームで遊んでいます。 このゲームでは、あなたは、勇者高橋くんとして人間界から魔法界に渡り、魔王と戦うことになります。 あなたは高橋くんの魔法の力を鍛え、ついに魔王を倒しました。 人間界と魔法界、ふたつの世界に平和が訪れましたが、これで物語が終わったわけではありません。 高橋くんは魔法界から人間界に帰還する必要があります。
魔法界と人間界をつなぐ通路は、1, 2, ..., N の番号がつけられた N 枚の扉と 1 つの魔法陣からなります。 魔法界から人間界に移動するためには、これら N 枚の扉を番号順に 1 回ずつ通り、その後魔法陣に入る必要があります。
魔法界には、魔法の帽子という特殊な帽子があります。 魔法界と人間界をつなぐ通路を通る際には、ちょうど 1 枚の扉を魔法の帽子をかぶって通り、それ以外のすべての扉を魔法の帽子をかぶらずに通る必要があります。
魔法界にいる人はそれぞれ魔法エネルギーを持っており、その大きさは通路の扉を通ることで後述のように変化します。 魔法陣に入る際には、安全のため、持っている魔法エネルギーの大きさは L 以上 R 以下となっている必要があります。
通路の扉を通った際の魔法エネルギーの大きさの変化は以下のとおりです。 大きさ x の魔法エネルギーを持つ人が扉 i を通ったとき、 通った後にその人が持つ魔法エネルギーの大きさ y は、 x, i の値およびその人が魔法の帽子をかぶっていたかどうかに応じて、
- 魔法の帽子をかぶっていなかった場合、
- x < i ならば y = x + i
- x \geq i ならば y = x - i
- 魔法の帽子をかぶっていた場合、x とi の大小関係によらず、y = x + i
となります。
高橋くんは、持っている魔法エネルギーの大きさが 0 の状態で、魔法の帽子を持って、魔法界と人間界をつなぐ通路に入りました。 魔法の帽子をかぶって通る扉の番号の選び方は N 通りありますが、このうち安全に魔法陣に入ることができる選び方は何通りあるか求めてください。
制約
- 1 \leq N \leq 10^{18}
- 0 \leq L \leq R \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N L R
出力
答えを 1 行で出力せよ。
入力例 1
3 5 7
出力例 1
1
扉 1 または扉 2 を通る際に魔法の帽子をかぶった場合、魔法エネルギーの大きさは 0 \rightarrow 1 \rightarrow 3 \rightarrow 0 と 変化します。 これらの扉を魔法の帽子をかぶって通る扉として選んだ場合、条件を満たしません。
扉 3 を通る際に魔法の帽子をかぶった場合、魔法エネルギーの大きさは 0 \rightarrow 1 \rightarrow 3 \rightarrow 6 と変化します。 この扉を魔法の帽子をかぶって通る扉として選んだ場合、条件を満たします。
以上より、条件を満たす帽子のかぶり方は 1 通り存在します。
入力例 2
5 67 89
出力例 2
0
入力例 3
1357 500 5000
出力例 3
1354