program shift
  implicit none
  integer(8), parameter :: modu = 998244353
  character(301) :: s
  integer :: k, n, a(302) = 0, m = 1, x = 0, h = 0, r, d, w, c, b, i, j
  integer(8) :: dp(0:300, 0:301) = 0
  read(*,*) s, k
  n = len_trim(s)
  s(n + 1:n + 1) = '0'
  do i = 1, n + 1
    if (s(i:i) == '0') then
      m = m + 1
      a(m) = x
    else
      x = x + 1
    end if
  end do
  k = min(k, x)
  dp(0, 0) = 1
  do i = 1, m - 1
    do j = h, 0, -1
      r = min(k - j, a(i + 1) - a(i))
      do d = 1, r
        w = j + d
        b = a(m) - a(i + 1) + d
        do c = 0, a(m) - a(i + 1)
          b = c + d
          dp(w, c) = dp(w, c) + dp(j, b)
          if (dp(w, c) > modu) dp(w, c) = dp(w, c) - modu
        end do
      end do
      do c = 1, a(m) - a(i + 1)
        dp(j, c) = dp(j, c) + dp(j, c - 1)
        if (dp(j, c) > modu) dp(j, c) = dp(j, c) - modu
      end do
    end do
    h = min(k, h + a(i + 1) - a(i))
  end do
  write(*,'(i0)') mod(sum(dp(0:h, 0)), modu)
end program shift
; ModuleID = 'FIRModule'
source_filename = "FIRModule"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@_QFEa = internal unnamed_addr global [302 x i32] zeroinitializer
@_QFEdp = internal unnamed_addr global [302 x [301 x i64]] zeroinitializer
@_QFEh = internal unnamed_addr global i32 0
@_QFEm = internal unnamed_addr global i32 1
@_QFEs = internal global [301 x i8] undef
@_QFEx = internal unnamed_addr global i32 0
@_QQcl.ca46ff119080f96d54b23f1acc78bf76 = linkonce constant [73 x i8] c"/home/ubuntu/Downloads/TheStack_IR/Collated/Fortran/Source_1148/source.f\00"
@_QQcl.30 = linkonce constant [1 x i8] c"0"
@_QQcl.28693029 = linkonce constant [4 x i8] c"(i0)"
@_QQEnvironmentDefaults = local_unnamed_addr constant ptr null

define void @_QQmain() local_unnamed_addr {
  %1 = alloca i32, align 4
  %2 = tail call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.ca46ff119080f96d54b23f1acc78bf76, i32 7)
  %3 = tail call i1 @_FortranAioInputAscii(ptr %2, ptr nonnull @_QFEs, i64 301)
  %4 = call i1 @_FortranAioInputInteger(ptr %2, ptr nonnull %1, i32 4)
  %5 = call i32 @_FortranAioEndIoStatement(ptr %2)
  br label %6

6:                                                ; preds = %0, %6
  %7 = phi i64 [ 300, %0 ], [ %11, %6 ]
  %8 = getelementptr [301 x [1 x i8]], ptr @_QFEs, i64 0, i64 %7
  %9 = load i8, ptr %8, align 1, !tbaa !3
  %10 = icmp eq i8 %9, 32
  %11 = add nsw i64 %7, -1
  %12 = icmp ne i64 %7, 0
  %13 = and i1 %10, %12
  br i1 %13, label %6, label %14

14:                                               ; preds = %6
  %.op = shl i64 %7, 32
  %sext = add i64 %.op, 8589934592
  %15 = ashr exact i64 %sext, 32
  %16 = select i1 %10, i64 1, i64 %15
  %17 = add nsw i64 %16, -1
  %18 = getelementptr [301 x [1 x i8]], ptr @_QFEs, i64 0, i64 %17
  %19 = load i8, ptr @_QQcl.30, align 1
  store i8 %19, ptr %18, align 1
  %20 = icmp sgt i64 %16, 0
  br i1 %20, label %.lr.ph, label %.._crit_edge_crit_edge

.._crit_edge_crit_edge:                           ; preds = %14
  %.pre = load i32, ptr @_QFEx, align 4, !tbaa !3
  br label %._crit_edge

.lr.ph:                                           ; preds = %14, %35
  %indvars.iv = phi i64 [ %indvars.iv.next, %35 ], [ 1, %14 ]
  %21 = add nsw i64 %indvars.iv, -1
  %22 = getelementptr [301 x [1 x i8]], ptr @_QFEs, i64 0, i64 %21
  %23 = call i32 @_FortranACharacterCompareScalar1(ptr %22, ptr nonnull @_QQcl.30, i64 1, i64 1)
  %24 = icmp eq i32 %23, 0
  br i1 %24, label %25, label %32

25:                                               ; preds = %.lr.ph
  %26 = load i32, ptr @_QFEm, align 4, !tbaa !3
  %27 = add i32 %26, 1
  store i32 %27, ptr @_QFEm, align 4, !tbaa !3
  %28 = load i32, ptr @_QFEx, align 4, !tbaa !3
  %29 = sext i32 %27 to i64
  %30 = add nsw i64 %29, -1
  %31 = getelementptr [302 x i32], ptr @_QFEa, i64 0, i64 %30
  store i32 %28, ptr %31, align 4, !tbaa !3
  br label %35

32:                                               ; preds = %.lr.ph
  %33 = load i32, ptr @_QFEx, align 4, !tbaa !3
  %34 = add i32 %33, 1
  store i32 %34, ptr @_QFEx, align 4, !tbaa !3
  br label %35

35:                                               ; preds = %25, %32
  %36 = phi i32 [ %28, %25 ], [ %34, %32 ]
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv, %16
  br i1 %exitcond.not, label %._crit_edge, label %.lr.ph

._crit_edge:                                      ; preds = %35, %.._crit_edge_crit_edge
  %37 = phi i32 [ %.pre, %.._crit_edge_crit_edge ], [ %36, %35 ]
  %38 = load i32, ptr %1, align 4, !tbaa !3
  %39 = call i32 @llvm.smin.i32(i32 %38, i32 %37)
  store i32 %39, ptr %1, align 4, !tbaa !3
  store i64 1, ptr @_QFEdp, align 16, !tbaa !3
  %40 = load i32, ptr @_QFEm, align 4, !tbaa !3
  %41 = add i32 %40, -1
  %42 = icmp sgt i32 %41, 0
  br i1 %42, label %.lr.ph61, label %122

.lr.ph61:                                         ; preds = %._crit_edge
  %43 = zext i32 %41 to i64
  %_QFEh.promoted = load i32, ptr @_QFEh, align 4, !tbaa !3
  %44 = sext i32 %40 to i64
  %45 = add nsw i64 %44, -1
  %46 = getelementptr [302 x i32], ptr @_QFEa, i64 0, i64 %45
  br label %47

47:                                               ; preds = %.lr.ph61, %._crit_edge59
  %indvars.iv79 = phi i64 [ 1, %.lr.ph61 ], [ %50, %._crit_edge59 ]
  %48 = phi i32 [ %_QFEh.promoted, %.lr.ph61 ], [ %121, %._crit_edge59 ]
  %49 = icmp sgt i32 %48, -1
  %50 = add nuw nsw i64 %indvars.iv79, 1
  %sext95 = shl i64 %50, 32
  %51 = ashr exact i64 %sext95, 32
  %52 = add nsw i64 %51, -1
  br i1 %49, label %.lr.ph58, label %.._crit_edge59_crit_edge

.._crit_edge59_crit_edge:                         ; preds = %47
  %.pre84 = add nsw i64 %indvars.iv79, -1
  %.phi.trans.insert85 = getelementptr [302 x i32], ptr @_QFEa, i64 0, i64 %.pre84
  %.pre86 = load i32, ptr %.phi.trans.insert85, align 4, !tbaa !3
  br label %._crit_edge59

.lr.ph58:                                         ; preds = %47
  %53 = xor i32 %48, -1
  %54 = sext i32 %53 to i64
  %55 = sub nsw i64 0, %54
  %56 = getelementptr [302 x i32], ptr @_QFEa, i64 0, i64 %52
  %57 = load i32, ptr %56, align 4, !tbaa !3
  %58 = add nsw i64 %indvars.iv79, -1
  %59 = getelementptr [302 x i32], ptr @_QFEa, i64 0, i64 %58
  %60 = load i32, ptr %59, align 4, !tbaa !3
  %61 = sub i32 %57, %60
  %62 = load i32, ptr %46, align 4, !tbaa !3
  %63 = sub i32 %62, %57
  %64 = sext i32 %63 to i64
  %65 = icmp sgt i32 %63, 0
  %66 = add nsw i64 %64, 1
  %67 = icmp sgt i32 %63, -1
  %xtraiter = and i64 %64, 1
  %68 = icmp eq i32 %63, 1
  %unroll_iter = and i64 %64, -2
  %lcmp.mod.not = icmp eq i64 %xtraiter, 0
  br label %69

69:                                               ; preds = %.lr.ph58, %._crit_edge56
  %70 = phi i64 [ %55, %.lr.ph58 ], [ %114, %._crit_edge56 ]
  %71 = phi i32 [ %48, %.lr.ph58 ], [ %113, %._crit_edge56 ]
  %72 = sub i32 %39, %71
  %73 = call i32 @llvm.smin.i32(i32 %72, i32 %61)
  %74 = icmp sgt i32 %73, 0
  br i1 %74, label %.lr.ph52, label %._crit_edge53

.lr.ph52:                                         ; preds = %69
  %75 = sext i32 %71 to i64
  br i1 %67, label %.lr.ph49.us.preheader, label %._crit_edge56

.lr.ph49.us.preheader:                            ; preds = %.lr.ph52
  %76 = zext i32 %73 to i64
  br label %.lr.ph49.us

.lr.ph49.us:                                      ; preds = %.lr.ph49.us.preheader, %._crit_edge50.us
  %indvars.iv72 = phi i64 [ 1, %.lr.ph49.us.preheader ], [ %indvars.iv.next73, %._crit_edge50.us ]
  %77 = phi i64 [ %76, %.lr.ph49.us.preheader ], [ %94, %._crit_edge50.us ]
  %78 = trunc i64 %indvars.iv72 to i32
  %79 = add i32 %71, %78
  %80 = sext i32 %79 to i64
  br label %81

81:                                               ; preds = %.lr.ph49.us, %81
  %indvars.iv69 = phi i64 [ 0, %.lr.ph49.us ], [ %indvars.iv.next70, %81 ]
  %82 = phi i64 [ %66, %.lr.ph49.us ], [ %92, %81 ]
  %83 = add nuw nsw i64 %indvars.iv69, %indvars.iv72
  %84 = getelementptr [302 x [301 x i64]], ptr @_QFEdp, i64 0, i64 %indvars.iv69, i64 %80
  %85 = load i64, ptr %84, align 8, !tbaa !3
  %sext96 = shl i64 %83, 32
  %86 = ashr exact i64 %sext96, 32
  %87 = getelementptr [302 x [301 x i64]], ptr @_QFEdp, i64 0, i64 %86, i64 %75
  %88 = load i64, ptr %87, align 8, !tbaa !3
  %89 = add i64 %88, %85
  %90 = icmp sgt i64 %89, 998244353
  %91 = add i64 %89, -998244353
  %spec.select.us = select i1 %90, i64 %91, i64 %89
  store i64 %spec.select.us, ptr %84, align 8, !tbaa !3
  %indvars.iv.next70 = add nuw nsw i64 %indvars.iv69, 1
  %92 = add nsw i64 %82, -1
  %93 = icmp sgt i64 %82, 1
  br i1 %93, label %81, label %._crit_edge50.us

._crit_edge50.us:                                 ; preds = %81
  %indvars.iv.next73 = add nuw nsw i64 %indvars.iv72, 1
  %94 = add nsw i64 %77, -1
  %95 = icmp sgt i64 %77, 1
  br i1 %95, label %.lr.ph49.us, label %._crit_edge53

._crit_edge53:                                    ; preds = %._crit_edge50.us, %69
  br i1 %65, label %.lr.ph55, label %._crit_edge56

.lr.ph55:                                         ; preds = %._crit_edge53
  %96 = sext i32 %71 to i64
  %.phi.trans.insert = getelementptr [302 x [301 x i64]], ptr @_QFEdp, i64 0, i64 0, i64 %96
  %.pre83 = load i64, ptr %.phi.trans.insert, align 8, !tbaa !3
  br i1 %68, label %._crit_edge56.loopexit.unr-lcssa, label %.lr.ph55.new

.lr.ph55.new:                                     ; preds = %.lr.ph55, %.lr.ph55.new
  %97 = phi i64 [ %spec.select45.1, %.lr.ph55.new ], [ %.pre83, %.lr.ph55 ]
  %indvars.iv75 = phi i64 [ %indvars.iv.next76.1, %.lr.ph55.new ], [ 1, %.lr.ph55 ]
  %niter = phi i64 [ %niter.next.1, %.lr.ph55.new ], [ 0, %.lr.ph55 ]
  %98 = getelementptr [302 x [301 x i64]], ptr @_QFEdp, i64 0, i64 %indvars.iv75, i64 %96
  %99 = load i64, ptr %98, align 8, !tbaa !3
  %100 = add i64 %97, %99
  %101 = icmp sgt i64 %100, 998244353
  %102 = add i64 %100, -998244353
  %spec.select45 = select i1 %101, i64 %102, i64 %100
  store i64 %spec.select45, ptr %98, align 8, !tbaa !3
  %indvars.iv.next76 = add nuw nsw i64 %indvars.iv75, 1
  %103 = getelementptr [302 x [301 x i64]], ptr @_QFEdp, i64 0, i64 %indvars.iv.next76, i64 %96
  %104 = load i64, ptr %103, align 8, !tbaa !3
  %105 = add i64 %spec.select45, %104
  %106 = icmp sgt i64 %105, 998244353
  %107 = add i64 %105, -998244353
  %spec.select45.1 = select i1 %106, i64 %107, i64 %105
  store i64 %spec.select45.1, ptr %103, align 8, !tbaa !3
  %indvars.iv.next76.1 = add nuw nsw i64 %indvars.iv75, 2
  %niter.next.1 = add i64 %niter, 2
  %niter.ncmp.1 = icmp eq i64 %niter.next.1, %unroll_iter
  br i1 %niter.ncmp.1, label %._crit_edge56.loopexit.unr-lcssa, label %.lr.ph55.new

._crit_edge56.loopexit.unr-lcssa:                 ; preds = %.lr.ph55.new, %.lr.ph55
  %.unr = phi i64 [ %.pre83, %.lr.ph55 ], [ %spec.select45.1, %.lr.ph55.new ]
  %indvars.iv75.unr = phi i64 [ 1, %.lr.ph55 ], [ %indvars.iv.next76.1, %.lr.ph55.new ]
  br i1 %lcmp.mod.not, label %._crit_edge56, label %._crit_edge56.loopexit.epilog-lcssa

._crit_edge56.loopexit.epilog-lcssa:              ; preds = %._crit_edge56.loopexit.unr-lcssa
  %108 = getelementptr [302 x [301 x i64]], ptr @_QFEdp, i64 0, i64 %indvars.iv75.unr, i64 %96
  %109 = load i64, ptr %108, align 8, !tbaa !3
  %110 = add i64 %.unr, %109
  %111 = icmp sgt i64 %110, 998244353
  %112 = add i64 %110, -998244353
  %spec.select45.epil = select i1 %111, i64 %112, i64 %110
  store i64 %spec.select45.epil, ptr %108, align 8, !tbaa !3
  br label %._crit_edge56

._crit_edge56:                                    ; preds = %._crit_edge56.loopexit.epilog-lcssa, %._crit_edge56.loopexit.unr-lcssa, %.lr.ph52, %._crit_edge53
  %113 = add i32 %71, -1
  %114 = add nsw i64 %70, -1
  %115 = icmp sgt i64 %70, 1
  br i1 %115, label %69, label %._crit_edge59

._crit_edge59:                                    ; preds = %._crit_edge56, %.._crit_edge59_crit_edge
  %116 = phi i32 [ %.pre86, %.._crit_edge59_crit_edge ], [ %60, %._crit_edge56 ]
  %117 = getelementptr [302 x i32], ptr @_QFEa, i64 0, i64 %52
  %118 = load i32, ptr %117, align 4, !tbaa !3
  %119 = add i32 %118, %48
  %120 = sub i32 %119, %116
  %121 = call i32 @llvm.smin.i32(i32 %39, i32 %120)
  %exitcond82.not = icmp eq i64 %indvars.iv79, %43
  br i1 %exitcond82.not, label %._crit_edge62, label %47

._crit_edge62:                                    ; preds = %._crit_edge59
  store i32 %121, ptr @_QFEh, align 4, !tbaa !3
  br label %122

122:                                              ; preds = %._crit_edge62, %._crit_edge
  %123 = call ptr @_FortranAioBeginExternalFormattedOutput(ptr nonnull @_QQcl.28693029, i64 4, ptr null, i32 -1, ptr nonnull @_QQcl.ca46ff119080f96d54b23f1acc78bf76, i32 39)
  %124 = load i32, ptr @_QFEh, align 4, !tbaa !3
  %125 = call i32 @llvm.smax.i32(i32 %124, i32 -1)
  %126 = sext i32 %125 to i64
  %.not = icmp slt i32 %124, 0
  br i1 %.not, label %_FortranASumInteger8x1_contract_simplified.exit, label %.lr.ph.i.preheader

.lr.ph.i.preheader:                               ; preds = %122
  %127 = add nsw i64 %126, 1
  %min.iters.check = icmp ult i64 %127, 4
  br i1 %min.iters.check, label %.lr.ph.i.preheader107, label %vector.ph

vector.ph:                                        ; preds = %.lr.ph.i.preheader
  %n.vec = and i64 %127, -4
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %vec.phi = phi <2 x i64> [ zeroinitializer, %vector.ph ], [ %131, %vector.body ]
  %vec.phi105 = phi <2 x i64> [ zeroinitializer, %vector.ph ], [ %132, %vector.body ]
  %128 = shl i64 %index, 3
  %129 = getelementptr i8, ptr @_QFEdp, i64 %128
  %wide.load = load <2 x i64>, ptr %129, align 16, !tbaa !3
  %130 = getelementptr i64, ptr %129, i64 2
  %wide.load106 = load <2 x i64>, ptr %130, align 16, !tbaa !3
  %131 = add <2 x i64> %wide.load, %vec.phi
  %132 = add <2 x i64> %wide.load106, %vec.phi105
  %index.next = add nuw i64 %index, 4
  %133 = icmp eq i64 %index.next, %n.vec
  br i1 %133, label %middle.block, label %vector.body, !llvm.loop !7

middle.block:                                     ; preds = %vector.body
  %bin.rdx = add <2 x i64> %132, %131
  %134 = call i64 @llvm.vector.reduce.add.v2i64(<2 x i64> %bin.rdx)
  %cmp.n = icmp eq i64 %127, %n.vec
  br i1 %cmp.n, label %_FortranASumInteger8x1_contract_simplified.exit.loopexit, label %.lr.ph.i.preheader107

.lr.ph.i.preheader107:                            ; preds = %.lr.ph.i.preheader, %middle.block
  %.ph = phi i64 [ 0, %.lr.ph.i.preheader ], [ %134, %middle.block ]
  %.ph108 = phi i64 [ 0, %.lr.ph.i.preheader ], [ %n.vec, %middle.block ]
  br label %.lr.ph.i

.lr.ph.i:                                         ; preds = %.lr.ph.i.preheader107, %.lr.ph.i
  %135 = phi i64 [ %140, %.lr.ph.i ], [ %.ph, %.lr.ph.i.preheader107 ]
  %136 = phi i64 [ %141, %.lr.ph.i ], [ %.ph108, %.lr.ph.i.preheader107 ]
  %137 = shl i64 %136, 3
  %138 = getelementptr i8, ptr @_QFEdp, i64 %137
  %139 = load i64, ptr %138, align 8, !tbaa !3
  %140 = add i64 %139, %135
  %141 = add nuw nsw i64 %136, 1
  %exitcond.not.i = icmp eq i64 %136, %126
  br i1 %exitcond.not.i, label %_FortranASumInteger8x1_contract_simplified.exit.loopexit, label %.lr.ph.i, !llvm.loop !10

_FortranASumInteger8x1_contract_simplified.exit.loopexit: ; preds = %.lr.ph.i, %middle.block
  %.lcssa = phi i64 [ %134, %middle.block ], [ %140, %.lr.ph.i ]
  %142 = srem i64 %.lcssa, 998244353
  br label %_FortranASumInteger8x1_contract_simplified.exit

_FortranASumInteger8x1_contract_simplified.exit:  ; preds = %_FortranASumInteger8x1_contract_simplified.exit.loopexit, %122
  %.lcssa.i = phi i64 [ 0, %122 ], [ %142, %_FortranASumInteger8x1_contract_simplified.exit.loopexit ]
  %143 = call i1 @_FortranAioOutputInteger64(ptr %123, i64 %.lcssa.i)
  %144 = call i32 @_FortranAioEndIoStatement(ptr %123)
  ret void
}

declare ptr @_FortranAioBeginExternalListInput(i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioInputAscii(ptr, ptr, i64) local_unnamed_addr

declare i1 @_FortranAioInputInteger(ptr, ptr, i32) local_unnamed_addr

declare i32 @_FortranAioEndIoStatement(ptr) local_unnamed_addr

declare i32 @_FortranACharacterCompareScalar1(ptr, ptr, i64, i64) local_unnamed_addr

declare ptr @_FortranAioBeginExternalFormattedOutput(ptr, i64, ptr, i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioOutputInteger64(ptr, i64) local_unnamed_addr

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.smin.i32(i32, i32) #0

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.smax.i32(i32, i32) #0

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(none)
declare i64 @llvm.vector.reduce.add.v2i64(<2 x i64>) #1

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #1 = { nocallback nofree nosync nounwind willreturn memory(none) }

!llvm.module.flags = !{!0, !1, !2}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{!4, !4, i64 0}
!4 = !{!"any data access", !5, i64 0}
!5 = !{!"any access", !6, i64 0}
!6 = !{!"Flang Type TBAA Root"}
!7 = distinct !{!7, !8, !9}
!8 = !{!"llvm.loop.isvectorized", i32 1}
!9 = !{!"llvm.loop.unroll.runtime.disable"}
!10 = distinct !{!10, !9, !8}
