338 : 長方形方眼紙の切断

整数の寸法$w × h$をもつ長方形の方眼紙がある. 罫線の間隔は1である. 罫線に沿って方眼紙を二つに切り離し, 二つを重なりなく並び替えると, 別の寸法の長方形を新たに作ることができる.

例えば,$9 × 4$の寸法の方眼紙からは, 下のように切って並び替えると, 寸法$18 × 2, 12 × 3, 6 × 6$の長方形を作ることができる.

p338_gridpaper.gif

同様に, 寸法$9 × 8$の方眼紙からは, 寸法$18 × 4, 12 × 6$の長方形を作ることができる.

$w$と$h$の組に対し, 寸法$w × h$の方眼紙から作ることができる異なる長方形の数を$F(w,h)$とする. 例えば,$F(2,1) = 0, F(2,2) = 1, F(9,4) = 3, F(9,8) = 2$である. 始めの長方形と合同な長方形は$F(w,h)$に数えないことに注意しよう. また寸法$w × h$と寸法$h × w$の長方形は別とみなさないことに注意しよう.

整数$N$に対し,$0 < h ≤ w ≤ N$を満たす全ての$w$と$h$の組に対する$F(w,h)$の和を$G(N)$とする. $G(10) = 55, G(10^3) = 971745, G(10^5) = 9992617687$であることが確かめられる.

$G(10^{12})$を求めよ. 答えを$\mod 10^8$で入力せよ.