問題を「\(10^9-R\) を持ってスタートし、\(10^9\) の倍数になったら終わり」と思うことにします。

これは absorbing markov chain の収束までの回数の期待値を求める問題ですが状態数が \(10^9\) あるのでそのまま計算することはできません。どうにかして状態数を減らすことを考えましょう。

少し考えると、状態がループしていない問題、「\(X\) を持ってスタートし、\(Y\) になったらクリア。\(Y\) を超えたらゲームオーバー。クリアできる確率と、クリアまでの操作回数の条件付き期待値を求めよ」であれば、行列累乗により高速に求めることができることがわかります。（確率と期待値を求めるDPを作り、遷移式を行列の形で書いてみましょう）

これにより、\(0\) をまたがない範囲の遷移をまとめて、状態を \(-5,\ldots,5\) の \(11\) 状態にすることができ、残りは十分高速に求めることができます。
（もちろん、\(0,\ldots,5\) の \(6\) 状態にまとめることもできますが、\(0\) をまたぐ遷移の部分と行列累乗でまとめる部分を分離した方がわかりやすいと個人的には思います）
注１：「absorbing markov chain において、遷移にコストがついており、収束までのコストの総和を求める」という問題は、コストが全て \(1\) の場合とほとんど同様の行列計算で求めることができます。考えてみましょう。
注２：\(10^9-R\) からスタートして初めて \(-5,\ldots,0\) に到達するまでは別途行列累乗で計算します。

出目の最大値を \(d\) として、全体で \(O(d^4 \log N)\) や \(O(d^4+d^3\log N)\) などの計算量で求めることができます。

この解法では、\(R\) に依存しない行列の逆行列を求める必要があり、この行列が mod 998244353 で正則であることは実際に計算してみるまで私にはわかりませんでした。