Problem 994

Counting Triangles

Given positive integers $m$ and $n$, for every $1\leq i \leq m$ and $1\leq j \leq n$ a line segment is drawn between points $(i,1)$ and $(j,2)$ in the plane. Then define $T(m,n)$ to be the number of triangles in the resulting picture, including those which are cut by other line segments.

Shown above is the example $m=2$, $n=3$, where eight triangles can be seen: four “smaller” triangles that are internally empty, and four “larger” triangles that are cut by another line segment. Thus $T(2,3)=8$.

You are also given $T(3,5)=146$ and $T(12,23)=756716$.

Find $T(1234\times 10^8,2345\times 10^8)$. Give your answer modulo $10^9+7$.

数三角形

给定正整数$m$和$n$，对于每一对满足$1\leq i \leq m$和$1\leq j \leq n$的整数$i$、$j$，在平面上作线段连接点$(i,1)$和$(j,2)$。定义$T(m,n)$为所得图形中所有三角形的数目，其中包括内部被线段切割成小三角形的大三角形。

如上图所示为$m=2$、$n=3$的例子，其中有八个三角形：四个内部为空的”小”三角形，以及四个内部被线段切割的”大”三角形；因此$T(2,3)=8$。

已知$T(3,5)=146$，$T(12,23)=756716$。

求$T(1234\times 10^8,2345\times 10^8)$，并对$10^9+7$取余作为你的答案。