TreeQwQ is busy dating with girls. There are $$$n$$$ time slots in a day numbered from $$$1$$$ to $$$n$$$. TreeQwQ is going on some dates today. He will give you a binary string $$$s$$$ to describe his schedule. $$$s_i = 1$$$ denotes TreeQwQ is dating in time slot $$$i$$$ while $$$s_i = 0$$$ denotes he is free in time slot $$$i$$$.

However, he finds his schedule boring because he has too many girls to date with. So you can help him by performing the following operation on his schedule exactly once.

• First, select an range $$$[l,r](1\leq l\leq r\leq n)$$$ such that there are exactly $$$k$$$ dating time slots from time slot $$$l$$$ to time slot $$$r$$$(inclusive).
• After selection, you can arbitrarily modify the states of the time slots(that is changing a time slot from dating to free, vice versa) from the $$$l$$$-th to the $$$r$$$-th time slot any times.
• After all the modifications, you need to guarantee that there are still exactly $$$k$$$ dating time slots from time slot $$$l$$$ to time slot $$$r$$$(inclusive).

TreeQwQ wants to know how many possible schedules he can get after performing the operation. Since the number may be very large. You need to tell TreeQwQ the number modulo $$$998244353$$$.

Note that two schedules are called different if there exists a time slot that TreeQwQ is dating in one schedule while he is free in the same time slot in the other schedule.