You are given 3 integers N, L and R. You need to find the sum of integers x, such that L≤x≤R and, x and N have some common divisor excluding 1. Since this sum can be too large, print it modulo 109+7.
Input Format
The input is a single line containing 3 space separated integers N, L and R.
Output Format
Print a single intger equal to the required sum modulo 109+7.
Constraints
1≤N≤1012
1≤L≤R≤1018
The values of x which satisfy the given conditions for N=12, L=5 and R=27 are 6,8,9,10,12,14,15,16,18,20,21,22,24,26,27. The sum of these numbers is equal to 248.