グリッド上の互いに素な移動 JavaScript編（paizaランク B 相当）

h × w のグリッドがあり、このグリッドの上から i 行目、左から j 列目のセルを (i, j) と呼ぶことにします。(1 ≦ i ≦ h, 1 ≦ j ≦ w)
あなたは最初に (1, 1) にいて、ちょうど k 回の移動で (h, w) にたどりつきたいと考えています。
ただし、移動は以下の条件を満たさなければなりません。

・ (i, j) から (i + dx, j + dy) に移動できるのは、gcd(dx, dy) = 1 であるとき、かつそのときに限る
・ ここで、gcd(x, y) は x と y の最大公約数とする
・ dx, dy は整数で、(dx, dy) ≠ (0, 0) を満たす (負でもよいことに注意)
・ グリッドの外に出るような移動はできない

以上の条件を満たすような経路の個数を求めてください。
ただし、経路 p は p = ((x_0, y_0), (x_1, y_1), ..., (x_k, y_k)) として表現され、
(x_0, y_0) = (1, 1)、(x_k, y_k) = (h, w) を満たします。
2 つの経路はその表現が異なる場合に別々の経路としてカウントするものとします。

答えは非常に大きくなる可能性があるため、10^9 で割った余りを出力してください。