직사각형 모양 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이 정수일 때, 범위 0 < h ≤ w ≤ N의 모든 w와 h쌍으로 계산한 F(w,h)의 합을 G(N)이라 합니다.
G(10) = 55, G(10³) = 971745 그리고 G(10⁵) = 9992617687 입니다.

G(10¹²)을 구하고 그 값을 10⁸으로 나눈 나머지를 답으로 제출하세요.