【cf477A】Dreamoon and Sums

2014年10月13日1,1180

Dreamoon loves summing up something for no reason. One day he obtains two integers aand b occasionally. He wants to calculate the sum of all nice integers. Positive integer x is called nice if and , where k is some integer number in range[1, a].

By we denote the quotient of integer division of x and y. By we denote the remainder of integer division of x and y. You can read more about these operations here: http://goo.gl/AcsXhT.

The answer may be large, so please print its remainder modulo 1 000 000 007 (109 + 7). Can you compute it faster than Dreamoon?

Input

The single line of the input contains two integers a, b (1 ≤ a, b ≤ 107).

Output

Print a single integer representing the answer modulo 1 000 000 007 (109 + 7).

Sample test(s)
input

output

input

output

Note

For the first sample, there are no nice integers because is always zero.

For the second sample, the set of nice integers is {3, 5}.

 

题解

求 ∑ x (div ( x , b) / mod ( x , b ) = k && 1<=k<=a)

设 m = mod ( x , b ) 则 x = m * k * b + m

1 <= m <= b – 1

则 ∑ x = ( k * b + 1 ) * b * ( b – 1 ) / 2 ,k可以直接枚举。。。