C - Shift Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

0 と 1 のみからなる文字列 S が与えられます。S に以下の操作を 0 回以上 K 回以下繰り返してできる可能性のある文字列の個数を 998244353 で割った余りを求めてください。

  • 整数 1\leq i < j\leq |S| の組であって、S の i 文字目が 0 であり j 文字目が 1 であるものを選ぶ。S の j 文字目を取り除き、i 文字目の直前の位置に挿入する。

制約

  • 1 \leq |S| \leq 300
  • 0 \leq K \leq 10^9
  • S は 0, 1 のみからなる

入力

入力は以下の形式で標準入力から与えられる。

S K

出力

S に操作を 0 回以上 K 回以下繰り返してできる可能性のある文字列の個数を 998244353 で割った余りを出力せよ。

入力例 1

0101 1

出力例 1

4

0101, 0110, 1001, 1010 の 4 通りの文字列ができる可能性があります。

入力例 2

01100110 2

出力例 2

14

入力例 3

1101010010101101110111100011011111011000111101110101010010101010101 20

出力例 3

113434815

Score : 800 points

Problem Statement

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

  • Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are 0 and 1, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

  • 1 \leq |S| \leq 300
  • 0 \leq K \leq 10^9
  • S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S K

Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Sample Input 1

0101 1

Sample Output 1

4

Four strings, 0101, 0110, 1001, and 1010, can result.

Sample Input 2

01100110 2

Sample Output 2

14

Sample Input 3

1101010010101101110111100011011111011000111101110101010010101010101 20

Sample Output 3

113434815