← Home
For problem statement at 1000-1999/1900-1999/1900-1909/1906/problemJ.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1900-1909/1906/verifierJ.go ends with reference runtime error: exit status 2
exit status 1 can you fix the verifier? ```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 998244353
const G = 3

func powMod(a, b int) int {
	res := 1
	for b > 0 {
		if b&1 == 1 {
			res = (res * a) % MOD
		}
		a = (a * a) % MOD
		b >>= 1
	}
	return res
}

func invMod(a int) int {
	return powMod(a, MOD-2)
}

var (
	wn  [30][]int
	iwn [30][]int
)

func initNTT() {
	for i := 0; i < 23; i++ {
		wn[i] = make([]int, 1<<i)
		iwn[i] = make([]int, 1<<i)
		w := powMod(G, (MOD-1)/(1<<i))
		iw := invMod(w)
		wn[i][0] = 1
		iwn[i][0] = 1
		for j := 1; j < (1 << i); j++ {
			wn[i][j] = (wn[i][j-1] * w) % MOD
			iwn[i][j] = (iwn[i][j-1] * iw) % MOD
		}
	}
}

func ntt(a []int, inv bool) {
	n := len(a)
	for i, j := 0, 0; i < n; i++ {
		if i < j {
			a[i], a[j] = a[j], a[i]
		}
		for k := n >> 1; (j^k)&k != 0; k >>= 1 {
			j ^= k
		}
		j ^= n >> 1
	}
	cnt := 1
	for k := 1; k < n; k <<= 1 {
		var w []int
		if inv {
			w = iwn[cnt]
		} else {
			w = wn[cnt]
		}
		for i := 0; i < n; i += k << 1 {
			for j := 0; j < k; j++ {
				u := a[i+j]
				v := (a[i+j+k] * w[j]) % MOD
				a[i+j] = (u + v) % MOD
				a[i+j+k] = (u - v + MOD) % MOD
			}
		}
		cnt++
	}
	if inv {
		invN := invMod(n)
		for i := 0; i < n; i++ {
			a[i] = (a[i] * invN) % MOD
		}
	}
}

func multiply(a, b []int) []int {
	n := 1
	for n < len(a)+len(b)-1 {
		n <<= 1
	}
	fa := make([]int, n)
	fb := make([]int, n)
	copy(fa, a)
	copy(fb, b)
	ntt(fa, false)
	ntt(fb, false)
	for i := 0; i < n; i++ {
		fa[i] = (fa[i] * fb[i]) % MOD
	}
	ntt(fa, true)
	return fa[:len(a)+len(b)-1]
}

func chirpZ(a []int, q, start, m int) []int {
	n := len(a)
	if n == 0 {
		return make([]int, m)
	}

	qk2 := make([]int, n+m)
	iqk2 := make([]int, n+m)

	curr := 1
	factor := 1 
	for k := 0; k < n+m; k++ {
		qk2[k] = curr
		iqk2[k] = invMod(curr)
		curr = (curr * factor) % MOD
		factor = (factor * q) % MOD
	}

	x := make([]int, n)
	p := 1
	for i := 0; i < n; i++ {
		p = (p * q) % MOD
		val := (a[i] * p) % MOD
		x[i] = (val * iqk2[i]) % MOD
	}

	y := make([]int, n+m-1)
	for i := 0; i < n+m-1; i++ {
		y[i] = qk2[i]
	}

	xr := make([]int, n)
	for i := 0; i < n; i++ {
		xr[i] = x[n-1-i]
	}

	conv := multiply(xr, y)

	res := make([]int, m)
	for k := 0; k < m; k++ {
		idx := k + n - 1
		if idx < len(conv) {
			val := (conv[idx] * iqk2[k]) % MOD
			res[k] = val
		}
	}
	return res
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &a[i])
	}

	if n == 1 {
		fmt.Println(1)
		return
	}

	initNTT()

	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, i+1)
	}

	store := make([][]int, n+1)

	inv2 := invMod(2)
	inv2Pow := make([]int, n+1)
	inv2Pow[0] = 1
	for i := 1; i <= n; i++ {
		inv2Pow[i] = (inv2Pow[i-1] * inv2) % MOD
	}

	dp[1][1] = 1

	if n > 1 {
		evals := make([]int, n)
		curr := 2
		for k := 0; k < n; k++ {
			evals[k] = curr
			curr = (curr * 2) % MOD
		}
		store[1] = evals
	}

	for i := 2; i <= n; i++ {
		P := 1
		D := 0
		W := 0

		for L := 1; L < i; L++ {
			prevEnd := i - L
			val := store[prevEnd][L-1]
			intra := powMod(2, L*(L-1)/2)
			
			term := (intra * powMod(2, W)) % MOD
			denomExp := (1 + D) * L
			denomExp %= (MOD - 1) 
			denom := powMod(2, denomExp)
			term = (term * invMod(denom)) % MOD
			term = (term * P) % MOD
			term = (term * val) % MOD
			dp[i][L] = term

			if i-L-1 >= 0 {
				u := a[i-L-1]
				v := a[i-L]
				if u < v {
					termP := (1 + inv2Pow[L]) % MOD
					P = (P * termP) % MOD
				} else {
					W = (W + D + 1) % (MOD - 1)
					D++
				}
			}
		}

		if i < n {
			coeffs := make([]int, i) 
			for L := 1; L <= i-1; L++ {
				coeffs[L] = dp[i][L]
			}
			res := chirpZ(coeffs, 2, 1, n-i)
			store[i] = res
		}
	}

	ans := 0
	for L := 1; L < n; L++ {
		ans = (ans + dp[n][L]) % MOD
	}
	fmt.Println(ans)
}
```