两个玩家玩两堆石头的游戏。他们轮流轮流。如果当前第一堆中有 $a$ 石头，第二堆中有 $b$ 石头，则一轮包括从第一堆中移除 $c\ge 0$ 石头并从第二堆中移除 $d\ge 0$，方式为 $ad-bc=\pm 1$。第一个清空其中一堆的玩家获胜。

请注意，只有当两堆大小互质时，该游戏才可以玩。

如果下一个玩家能够以最佳发挥保证获胜，则游戏状态 $(a,b)$ 就是获胜位置。定义 $H(N)$ 为获胜位置 $(a,b)$ 的数量，其中 $gcd(a,b)=1$，$a>0$,$b>0$ 和 $a+b\le N$。请注意顺序很重要，例如 $(2,1)$ 和 $(1,2)$ 是不同的位置。

您获得 $H(4)=5$ 和 $H(100)=2043$。

求$H({10}^9)$。