-- Your code here!
import Data.Bits
b2i xs = foldl (\x y -> 2 * x + y) 0 $ map (\x -> read [x]) xs

main = print =<< solve <$> ((\[a,b] -> [0, b2i b, fromIntegral $ length b]) <$> words <$> getLine) <*> ((fmap b2i) <$> lines <$> getContents)

solve :: [Integer] -> [Integer] -> Integer
solve (_:x:xn:_) (a:bs) = mod (conf + obv a) 998244353 where
    obv a
        |a == 1 = x - conf + 1
        |otherwise = filterSum (x >=) (fmap (xorProduct (spBit bas)) [conf..conf*2])
    conf = 2 ^ (xn - count bas)
    bas = base a bs
    filterSum _pred []    = 0
    filterSum pred (x:xs)
        | pred x         = 1 + filterSum pred xs
        | otherwise      = filterSum pred xs
base 1 _ = 1
base a [] = a
base a (b:bs) = base (f a b) bs where
    f 0 b = b
    f 1 _ = 1
    f a b 
        |a == b = a
        |otherwise = f (g a b) (min a b)
    g a b = let amb = count a - count b in xor (sl a (-amb)) (sl b amb)
    sl a b = if (b > 0) then shiftL a b else a
count a = h a 0 where
    h 0 s = s
    h a s = h (shiftR a 1) (s + 1)
xorProduct a b = foldr1 xor (fmap (b*) a)
spBit a = zipWith (*) (iterate (*2) 1) (f a) where
    f 0 = []
    f a = mod a 2 : f (div a 2)