　一回で移動できる正整数の組に有向辺を張ると, 以下のようなグラフを得る (自己辺や多重辺は適当に除去).
![figure 1](\/images\/sslBjEvefjMEoeD0mOUXS83t9c8uSmGNrIh30w8b)

　$50000005000000$ は三角数であるから, 上から $10^7$ 段のみ考えればよい. 辺の傾きは $3$ 種類存在するが, 最短経路として適するものでは高々 $2$ 種類しか用いない. このうち,対称性より横向きの辺を使わず, 上から下へ向かうものを数えればよい. このとき, 下から $n$ 段目のある固定された数から下から $m$ 段目への最短経路の数は $2^{n-m}$ 通りであるから, これをすべての $m$ について足し合わせれば $2^n-2$ 通りである. したがって, 考えている経路の総数は
$$\begin{aligned}
&\quad\\,\\, (2^{10000000}-2) \times 1+(2^{9999999}-2) \times 2+\cdots+(2^1-2) \times 10000000\\\\
&=(2^{10000001}-2 \times 10000001)+(2^{10000000}-2 \times 10000000)+\cdots +(2^2-2 \times 2)\\\\
&=2^{10000002}-100000030000004
\end{aligned}$$
　他の $2$ 方向も同様であるが, $1$ 種類の向きしか使わない経路が重複でカウントされているため,
$$\begin{aligned}
&\quad\\,\\, 3 \times(2^{10000002}-100000030000004)-3\times\sum_{i=1}^{10^7}\dfrac{n(n-1)}{2}\\\\
&=3 \times 2^{10000002}-500000300000085000012
\end{aligned}$$
以上より, 解答すべき値は $\textbf{300000095000017}$ である.
公式解説
https://onlinemathcontest.com/contests/omc053/editorial/1446
　数直線上の正整数 $a$ の位置にいるsimasima君は, 正整数 $b$ の位置にいるPCT君に会いたいです.\
　simasima君が位置 $x$ にいるとき, 以下の $6$ 条件のうち $1$ つ以上をみたす**正整数**の位置に一回で移動できます：

- $x+1$
- $x-1$
- $x$ **未満**で最大の三角数 $y$ について, $2y-x+2$　($x=1$ では考えない)
- $x$ **以下**で最大の三角数 $z$ について, $2z-x+1$
- $x$ **以上**で最小の三角数 $s$ について, $2s-x+1$
- 上と同じ $s$ について, $2s-x+2$

　このとき, simasima君が位置 $b$ まで最小回数で移動する経路が $f(a,b)$ 種類存在するとします. 例えば
$$f(20,21)=1$$
です. ここで, 上で述べた条件のうち複数から同時に同じ正整数が得られる場合でも, それらは経路として同一視します. このとき, 以下をみたす正整数の組 $(a,b)$ すべてについて, $f(a,b)$ の総和 $M$ を求めてください.
$$a\lt b\leq 50000005000000=\dfrac{10^7\times(10^7+1)}{2}$$ 
　ただし, 奇数 $i$ および正整数 $j\geq 1000$, $k\leq 10^{100}$ によって
$$M=i\times2^j-k$$
と一意に表されるので, $i+j+k$ を $10^{15}$ で割った余りを解答して下さい. \
　ここで**三角数**とは, ある正整数 $n$ について $1+2+\cdots+n$ の形式に表せる正整数のことを指します.