Consider the expected value \(E _ i\) of the number of operations until the procedure ends, starting fro mthe state where \(X\) satisfies \(R-X\equiv i\pmod{10^9}\).

Until \(X-R\geq k10^9\), we always reach the state where \(X-R=k10^9-1,k10^9-2,k10^9-3,k10^9-4,k10^9-5,k10^9-6\), so \(E _ 1,E _ 2,E _ 3,E _ 4,E _ 5,E _ 6\) can be expressed solely by \(E _ 1,E _ 2,E _ 3,E _ 4,E _ 5,E _ 6\).

Consider the following problem.

Problem

You are given an integer \(r\). We repeatedly cast a die and subtract the shown number from \(r\). Once \(r\leq 0\), we terminate the procedure. Find the expected value \(e( r )\) of the number of of casting the die until the procedure terminates, and the probability \(p _ i\) that the resulting value \(r\) equals \(i\) for \(i=0,-1,-2,-3,-4,-5\).

Since these have linear recurrence relations, one can find this in an \(O(\log r)\) for a given \(r\) (if the die is \(d\)-sided, it can be solved in an \(O(d^2\log d\log r)\) time).

Thus, we obtain six equations that \(E _ i\ (i=1,2,3,4,5,6)\) satisfy. Solving them yields \(E _ i\). The time complexity is about \(O(d^3\log d\log r)\). Since it is independent of the input, we can precalculate them.

Then answer to this problem is \(\displaystyle e(R-6)+\sum _ {i=1} ^ 6E _ ip _ {i-6}(R-6)\).

Thus, the problem has been solved in a total of \(O(\log r)\) time.