Problem Courtesy: Ovishek Paul

Department of CSE, SUST

Sylhet, Bangladesh.

.........................................................................................................

Bodi is a "hotash" programmer. Sometimes he writes some code that takes 2777778 hours!!!

Good programmers said Bodi to become efficient. But Bodi just can't be. So he writes another code of  2777778 hours! which is below -

long long sum = 0;

for(long long i = L; i<=R; i++){
          sum += i % mod;
          sum %= (109 + 7);
}

where, 1 <= L <= R <= 10¹⁸ , 1 <= mod <= 10¹⁸

Now Bodi is here to you because Bodi recently have known that you are so efficient!!!

Input

First line will contain 3 integers L, R, and mod.

Output

Just print the final sum.

Example

Input:
4 5 6
Output:
9

Input:
4 10 9

Output:
31