# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hange has developed a special gear to attack the Cart Titan. The gear is a round, disc-like object. Its front surface is smooth but the rear surface has **N** small, equal-sized cells along the perimeter. These cells can charge deadly shrapnel. To assemble a gear, Hange picks a sequence of **N**, not necessarily distinct, positive integers and assigns them to the **N** cells. She calls this sequence an assembly. For demonstration purpose, she has sketched a prototypical figure of a gear with **N=4**.

The laziness of a cell is the number assigned to it by Hange which denotes the interval between two shrapnel charges of the cell. If we assume that the gear is thrown around the Titan’s neck at time **T = 0** and a cell’s laziness is **L**, then the cell will charge shrapnels at times **T =** **L**, **2L**, **3L** and so on. Although, there’s a small flaw in the current design. When all the **N** cells charge at the same time, the gear explodes on itself immediately after the charge. Once the gear explodes, none of its cell can function anymore.

The Cart Titan is well known for its endurance. It builds a protective shield along its neck as soon as it sees the gear and sadly, the gear can’t do any damage to the shield, let alone kill the Titan. There’s a slim chance though, as Hange came to know that at time **T = K _{1}** the shield becomes unstable and it remains unstable until

The only line will consist of three integers, **N**, **K _{1}** and

**1 ≤ N, K _{1}, K_{2} ≤10^{9}, 0 ≤ K_{2} - K_{1} ≤ 10^{6}**

Print a single line containing the number of ways modulo **10 ^{9}+7**.

Input | Output |
---|---|

4 3 3 | 5 |

Input | Output |
---|---|

4 9 10 | 77 |

Two of the several other valid assemblies are On the other hand, |

Login to submit

Burnside’s Lemma, Principle of Inclusion-Exclusion / Multiplicative function, Segmented Sieve, Memor...