# SOLUTION

Cheems’ girlfriend Cheema left him and went to Doge because he was bad at maths. The reason behind this was that when they were attending a maths lecture (Cheema’s favorite subject), her best friend Doge answered the mathematical question asked by the professor before Cheems.

This was shocking for Cheema, so she decided to leave him (Akhir Wafa ke badle Wafa kyu nhi milti). This was unbelievable for Cheems, so he decided to crack UPSC (Thukra ke mera pyar mera inteqam dekhegi). So the first problem he came across was as follows:-

You are given three integers LLRR, and SS. Find the total number of subsets wherein the summation of the total number of prime factors of distinct numbers (lying between LL and RR both inclusive) is equal to SS.

The prime factor of a number is that divisor which has a factor as 1 and that number itself only. Can you help Cheems to solve this question?

### Input Cheems VS Doge solution codechef

The only line of the input contains three integers – LLRRSS.

### Output Cheems VS Doge solution codechef

Print answer to the given problem. Since the answer can be large, print answer modulo 1000000007 (109+7)(109+7).

1LR1061≤L≤R≤106
|RL|103|R−L|≤103
1S1031≤S≤103

### Sample Input Cheems VS Doge solution codechef

6 14 5


### Sample Output Cheems VS Doge solution codechef

71


### Explanation

We need to calculate no. of prime divisors for each integer between 6 to 14 (both inclusive): 2,1,1,1,2,1,2,1,22,1,1,1,2,1,2,1,2
Now we need to find no. of subsets such that sum of subset of this array is 5

There are 3 ways:
2+2+1: 30 ways
2+1+1+1: 40 ways
1+1+1+1+1: 1 way

Total 71 ways.