# 338 : 長方形方眼紙の切断

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

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

![p338\_gridpaper.gif](https://projecteuler.net/project/images/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$$で入力せよ.
