prime_set

Chaque testcase contient 3 entiers, N, low et high tous les trois compris au sens large entre 1 et 100.000 et low est inférieur à high. Le but est de compter le nombre de séquences de N entiers compris au sens large entre low et high (à ce point il y en a donc (high-low+1)^N) telles que le plus grand diviseur commun à la séquence soit 1.

Par exemple pour le testcase: 2 2 4. Il y a 9 séquences: (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,2), (4,3), (4,4). Mais seules les séquences (2,3), (3,2), (3,4) et (4,3) vérifient la condition sur le pgcd.

Le résultat pouvant être grand vous devez le calculer modulo 1.000.000.007

Input

1 1 10
2 2 4
2 5 5
1 42 42
222 1 100

Télécharger l'entrée

Output

1
4
0
0
339886855

Télécharger la sortie