```go
package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

const MOD int64 = 998244353
const MAXN = 100000

var data []byte
var ptr int

func nextInt() int {
	for ptr < len(data) && data[ptr] <= ' ' {
		ptr++
	}
	sign := 1
	if data[ptr] == '-' {
		sign = -1
		ptr++
	}
	val := 0
	for ptr < len(data) && data[ptr] > ' ' {
		val = val*10 + int(data[ptr]-'0')
		ptr++
	}
	return val * sign
}

func nextString() string {
	for ptr < len(data) && data[ptr] <= ' ' {
		ptr++
	}
	start := ptr
	for ptr < len(data) && data[ptr] > ' ' {
		ptr++
	}
	return string(data[start:ptr])
}

func modPow(a, e int64) int64 {
	res := int64(1)
	for e > 0 {
		if e&1 == 1 {
			res = res * a % MOD
		}
		a = a * a % MOD
		e >>= 1
	}
	return res
}

var fac []int64
var ifac []int64
var pow2 []int64

func initComb() {
	fac = make([]int64, MAXN+1)
	ifac = make([]int64, MAXN+1)
	pow2 = make([]int64, MAXN+1)
	fac[0] = 1
	pow2[0] = 1
	for i := 1; i <= MAXN; i++ {
		fac[i] = fac[i-1] * int64(i) % MOD
		pow2[i] = pow2[i-1] * 2 % MOD
	}
	ifac[MAXN] = modPow(fac[MAXN], MOD-2)
	for i := MAXN; i >= 1; i-- {
		ifac[i-1] = ifac[i] * int64(i) % MOD
	}
}

func C(n, k int) int64 {
	if k < 0 || k > n {
		return 0
	}
	return fac[n] * ifac[k] % MOD * ifac[n-k] % MOD
}

func evalState(c0, c1 int) byte {
	if c0 > 0 && c1 > 0 {
		return 3
	}
	if c0 > 0 {
		return 1
	}
	if c1 > 0 {
		return 2
	}
	return 0
}

func main() {
	initComb()
	data, _ = io.ReadAll(os.Stdin)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := nextInt()
	for ; t > 0; t-- {
		n := nextInt()
		k := nextInt()
		s := []byte(nextString())

		L := k - 1
		m := L / 2
		P := n - k + 1

		prefixFixed0Total, prefixFixed1Total := 0, 0
		for i := 0; i < P; i++ {
			if s[i] == '0' {
				prefixFixed0Total++
			} else if s[i] == '1' {
				prefixFixed1Total++
			}
		}

		tailFixed1, tailQ := 0, 0
		for i := P; i < n; i++ {
			if s[i] == '1' {
				tailFixed1++
			} else if s[i] == '?' {
				tailQ++
			}
		}

		var below int64
		upper := m - 1 - tailFixed1
		if upper > tailQ {
			upper = tailQ
		}
		for x := 0; x <= upper; x++ {
			below += C(tailQ, x)
			if below >= MOD {
				below -= MOD
			}
		}
		equal := C(tailQ, m-tailFixed1)
		above := (pow2[tailQ] - below - equal + 2*MOD) % MOD

		var ans int64
		if prefixFixed1Total == 0 {
			ans += below
		}
		if prefixFixed0Total == 0 {
			ans += above
		}
		ans %= MOD

		cnt0 := make([]int, L)
		cnt1 := make([]int, L)
		for pos := 1; pos <= n; pos++ {
			r := (pos - 1) % L
			if s[pos-1] == '0' {
				cnt0[r]++
			} else if s[pos-1] == '1' {
				cnt1[r]++
			}
		}

		state := make([]byte, L)
		freeCnt, forced0Cnt, forced1Cnt, confCnt := 0, 0, 0, 0

		addState := func(st byte, delta int) {
			switch st {
			case 0:
				freeCnt += delta
			case 1:
				forced0Cnt += delta
			case 2:
				forced1Cnt += delta
			case 3:
				confCnt += delta
			}
		}

		for r := 0; r < L; r++ {
			st := evalState(cnt0[r], cnt1[r])
			state[r] = st
			addState(st, 1)
		}

		waysBalanced := func() int64 {
			if confCnt > 0 {
				return 0
			}
			need := m - forced1Cnt
			if need < 0 || need > freeCnt {
				return 0
			}
			return C(freeCnt, need)
		}

		waysNeed := func(r int, v int) int64 {
			if confCnt > 0 {
				return 0
			}
			st := state[r]
			if st == 3 {
				return 0
			}
			if st == 1 {
				if v == 0 {
					return waysBalanced()
				}
				return 0
			}
			if st == 2 {
				if v == 1 {
					return waysBalanced()
				}
				return 0
			}
			need := m - forced1Cnt - v
			if need < 0 || need > freeCnt-1 {
				return 0
			}
			return C(freeCnt-1, need)
		}

		ans += waysBalanced()
		if ans >= MOD {
			ans -= MOD
		}

		pref0, pref1 := 0, 0
		for b := 1; b <= P; b++ {
			ch := s[b-1]
			if ch == '0' {
				pref0++
			} else if ch == '1' {
				pref1++
			}

			r := (b - 1) % L
			addState(state[r], -1)
			if ch == '0' {
				cnt0[r]--
			} else if ch == '1' {
				cnt1[r]--
			}
			state[r] = evalState(cnt0[r], cnt1[r])
			addState(state[r], 1)

			if pref0 > 0 && pref1 > 0 {
				continue
			}
			if pref0 > 0 {
				ans += waysNeed(r, 1)
			} else if pref1 > 0 {
				ans += waysNeed(r, 0)
			} else {
				ans += waysBalanced()
			}
			if ans >= MOD {
				ans %= MOD
			}
		}

		out.WriteString(strconv.FormatInt(ans%MOD, 10))
		out.WriteByte('\n')
	}
}
```