For problem statement at 0-999/900-999/910-919/913/problemF.txt this is a correct solution, but verifier at 0-999/900-999/910-919/913/verifierF.go ends with case 2 failed: input=3 3 1
expected 3 got 570425345 can you fix the verifier? An implementation in Go that solves the problem.
```go
package main
import (
"bufio"
"fmt"
"os"
)
const MOD = 998244353
func add(a, b int64) int64 {
return (a + b) % MOD
}
func sub(a, b int64) int64 {
return (a - b + MOD) % MOD
}
func mul(a, b int64) int64 {
return (a * b) % MOD
}
func power(a, b int64) int64 {
res := int64(1)
for b > 0 {
if b&1 != 0 {
res = mul(res, a)
}
a = mul(a, a)
b >>= 1
}
return res
}
func modInverse(n int64) int64 {
return power(n, MOD-2)
}
func main() {
reader := bufio.NewReader(os.Stdin)
var n int
var a, b int64
fmt.Fscan(reader, &n, &a, &b)
p := mul(a, modInverse(b))
q := sub(1, p)
// Precompute powers
powP := make([]int64, n+1)
powQ := make([]int64, n+1)
powP[0] = 1
powQ[0] = 1
for i := 1; i <= n; i++ {
powP[i] = mul(powP[i-1], p)
powQ[i] = mul(powQ[i-1], q)
}
// W[k] will store W[i][k] for the current iteration i
W := make([]int64, n+1)
prevW := make([]int64, n+1)
// Base case W[0][0] = 1, essentially
prevW[0] = 1
sc := make([]int64, n+1)
dp := make([]int64, n+1)
nC2 := make([]int64, n+1)
for i := 0; i <= n; i++ {
val := int64(i) * int64(i-1)
val /= 2
nC2[i] = val % MOD
}
for i := 1; i <= n; i++ {
// Compute W[i][j] using prevW (which is W[i-1])
// W[i][j] = q^{i-j} * W[i-1][j-1] + p^j * W[i-1][j]
// W[i][0] = q^i * W[i-1][-1] + p^0 * W[i-1][0] = W[i-1][0]
W[0] = prevW[0]
for j := 1; j < i; j++ {
term1 := mul(powQ[i-j], prevW[j-1])
term2 := mul(powP[j], prevW[j])
W[j] = add(term1, term2)
}
// W[i][i] = q^0 * W[i-1][i-1] + p^i * W[i-1][i] = W[i-1][i-1]
W[i] = prevW[i-1]
// Calculate sc[i]: probability that a tournament of size i is strongly connected
// sc[i] = 1 - sum_{j=1}^{i-1} sc[j] * W[i][j]
sumSc := int64(0)
for j := 1; j < i; j++ {
term := mul(sc[j], W[j])
sumSc = add(sumSc, term)
}
sc[i] = sub(1, sumSc)
// Calculate dp[i]: expected number of games for n=i
if i == 1 {
dp[1] = 0
} else {
sumDp := int64(0)
for j := 1; j < i; j++ {
// Additional games: dp[j] for the first component + dp[i-j] for the rest
// However, the "rest" part is calculated as if they start fresh, but they already played \binom{i-j}{2} games in the current round.
// Correct recurrence term: dp[j] + (dp[i-j] - \binom{i-j}{2})
cost := add(dp[j], dp[i-j])
cost = sub(cost, nC2[i-j])
term := mul(sc[j], W[j])
term = mul(term, cost)
sumDp = add(sumDp, term)
}
// dp[i] = (nC2[i] + sumDp) / (1 - sc[i])
num := add(nC2[i], sumDp)
den := sub(1, sc[i])
dp[i] = mul(num, modInverse(den))
}
// Update prevW for next iteration
for k := 0; k <= i; k++ {
prevW[k] = W[k]
}
}
fmt.Println(dp[n])
}
```