The Humongous Sum

5

1 votes
Hard
Problem

You are given 3 integers NL and R. You need to find the sum of integers x, such that LxR  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

1N1012

1LR1018

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?