No.886 Direct
タグ : / 解いたユーザー数 62
作問者 :
QCFium
/ テスター :
tempura_pp
Problem Statement
The time limit for this problem is 4 seconds.
$HW$ points are arranged in an evenly spaced $H \times W$ grid.
Find the number of line segments that connect 2 distinct points among them and do not pass through any point other than those 2 points.
Here, two line segments are considered different if they are different as geometric figures.
Also, since the answer can get fairly large, output the answer modulo $10^9+7$.
Input
$H \hspace{7pt} W$
$1 \le H \le 3 \times 10^6$
$1 \le W \le 3 \times 10^6$
$H$ and $W$ are integers.
Output
Output the number of line segments satisfying the conditions in the problem statement, modulo $10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
2 2
Output
6
In this case, every line segment connecting a pair of 2 distinct points satisfies the condition.
Sample 2
Input
1 1
Output
0
There are no line segments connecting 2 distinct points in the first place.
Sample 3
Input
2 3
Output
13
The 6 points are arranged as follows.
. . . . . .All $3 \times 3 = 9$ line segments connecting the upper row and the lower row satisfy the condition. Among the line segments connecting points within the upper row, only the $2$ connecting adjacent points satisfy the condition, and the same applies to the lower row.
Therefore, $9 + 2 + 2 = 13$ line segments satisfy the condition.
Sample 4
Input
41279 3235
Output
0
Output the answer modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。