Let’s try to solve this using dynamic programming (DP). We could define \(dp[i, j]\) to be “the probability that the \(j\)-th person in the line will be the last person remaining, if there are \(i\) people in the line”. Base case: \(dp[1, 1] = 1\).

Let’s try to solve each \(dp[i, *]\) by increasing \(i\). The transition is relatively simple: \(dp[i, 1] = dp[i, i] / 2\), and \(dp[i, j] = (dp[i-1, j-1] + dp[i, j-1]) / 2\) for \(2 \le j \le i\).

One issue that comes up is that the transitions form a cycle, which is usual in probability problems involving an indefinitely-repeating process. We could solve that issue by defining a variable \(x := dp[i, 1]\), that way we could calculate the rest of \(dp[i, *]\) via equations of the form \(dp[i, j] = ax + b\). Once we have done so, we can then find an equation for \(dp[i, 1]\), and use this to solve for \(x\), and thus find definite values for all \(dp[i, *]\).

The problem is thus solved in \(O(N^2)\).

Bonus exercise: Prove that under the problem constraints, whenever you solve \(x = ax + b \implies x = \large\frac b {1-a}\), that \(1-a \not\equiv 0 \pmod {998244353}\), which would otherwise cause issues with performing such a division with modular residues.