Возьмем прямоугольный лист бумаги в клеточку размерами w × h. Шаг клетки составляет 1.
Если разрезать такой лист по границам клеток и совместить полученные куски без перекрытия, то можно образовать прямоугольники других размеров.

К примеру, из листа рамерами 9 × 4 , можно создать прямоугольники размерами 18 × 2, 12 × 3 и 6 × 6, если разрезать и соединить полученные куски, как это показано ниже:

Аналогично, из листа размерами 9 × 8 , можно образовать прямоугольники размерами 18 × 4 и 12 × 6 .

Для пары чисел w и h определим F(w,h) как количество отличных прямоугольников, которые можно образовать из листа бумаги размерами 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 определим G(N) в виде суммы F (w,h) для всех тех пар w и h, которые удовлетворяют требованию 0 < h ≤ w ≤ N.
Можно убедиться, что G(10) = 55, G(10³) = 971745 и G(10⁵) = 9992617687.

Найдите G(10¹²). Ответ приведите по модулю 10⁸.