program main
    implicit none
    character(101):: s
    integer(8):: dp(0:1,0:3,0:105)=0, k, n
    integer(4):: i1, i2, i3, d, i
    integer(4):: nd, ni1,ni2,ni3, ans=0

    read*, s
    read*, k
    n = len_trim(s)
    dp(0,0,0) = 1


    do i1=0, n-1
        do i2=0, 3
            do i3=0, 1
                read(s(i1+1:i1+1),*) nd
                do d=0,9
                    ni1 = i1+1; ni2 = i2; ni3 = i3 
                    if (d /= 0) ni2=ni2+1
                    if (ni2 > k) cycle
                    if (i3==0) then
                        if (d > nd) cycle
                        if (d < nd) ni3=1
                    end if
                    dp(ni3,ni2,ni1) = dp(ni3,ni2,ni1) + dp(i3,i2,i1)
                end do
            end do
        end do
    end do
    do i=0,n
        ! print*,'--'
        ! print*, dp(0,:,i)
        ! print*, dp(1,:,i)
    end do
    ans = dp(0,k,n)+dp(1,k,n)

    print*, ans
end program main
; 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"

@_QFEans = internal unnamed_addr global i32 0
@_QFEdp = internal unnamed_addr global [106 x [4 x [2 x i64]]] zeroinitializer
@_QFEs = internal global [101 x i8] undef
@_QQcl.dc03768eea24ae936d9c97250a8c3b66 = linkonce constant [73 x i8] c"/home/ubuntu/Downloads/TheStack_IR/Collated/Fortran/Source_2473/source.f\00"
@_QQEnvironmentDefaults = local_unnamed_addr constant ptr null

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

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

17:                                               ; preds = %9
  %18 = shl i64 %10, 32
  %sext = add i64 %18, 4294967296
  %19 = ashr exact i64 %sext, 32
  %20 = select i1 %13, i64 0, i64 %19
  store i64 1, ptr @_QFEdp, align 16, !tbaa !3
  %21 = trunc i64 %20 to i32
  %22 = icmp sgt i32 %21, 0
  br i1 %22, label %.preheader47.preheader, label %.._crit_edge_crit_edge

.._crit_edge_crit_edge:                           ; preds = %17
  %.pre = load i64, ptr %1, align 8, !tbaa !3
  br label %._crit_edge

.preheader47.preheader:                           ; preds = %17
  %wide.trip.count = and i64 %20, 4294967295
  br label %.preheader47

.preheader47:                                     ; preds = %.preheader47.preheader, %136
  %indvars.iv85 = phi i64 [ 0, %.preheader47.preheader ], [ %indvars.iv.next86, %136 ]
  %indvars.iv.next86 = add nuw nsw i64 %indvars.iv85, 1
  %sext89 = shl i64 %indvars.iv.next86, 32
  %23 = ashr exact i64 %sext89, 32
  %24 = add nsw i64 %23, -1
  %25 = getelementptr [101 x [1 x i8]], ptr @_QFEs, i64 0, i64 %24
  br label %.preheader

.preheader:                                       ; preds = %.preheader47, %135
  %indvars.iv63 = phi i64 [ 0, %.preheader47 ], [ %indvars.iv.next64, %135 ]
  %26 = add nuw nsw i64 %indvars.iv63, 1
  %27 = add nuw nsw i64 %indvars.iv63, 1
  br label %28

28:                                               ; preds = %.preheader, %.split53.us
  %indvars.iv = phi i64 [ 0, %.preheader ], [ %indvars.iv.next, %.split53.us ]
  %29 = call ptr @_FortranAioBeginInternalListInput(ptr %25, i64 1, ptr null, i64 0, ptr nonnull @_QQcl.dc03768eea24ae936d9c97250a8c3b66, i32 17)
  %30 = call i1 @_FortranAioInputInteger(ptr %29, ptr nonnull %2, i32 4)
  %31 = call i32 @_FortranAioEndIoStatement(ptr %29)
  %32 = load i64, ptr %1, align 8, !tbaa !3
  %33 = icmp eq i64 %indvars.iv, 0
  %34 = load i32, ptr %2, align 4
  %35 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %indvars.iv85, i64 %indvars.iv63, i64 %indvars.iv
  %.not45.us = icmp slt i64 %32, %indvars.iv63
  br i1 %33, label %.split.us.preheader, label %.split

.split.us.preheader:                              ; preds = %28
  %36 = icmp slt i32 %34, 0
  %or.cond = select i1 %.not45.us, i1 true, i1 %36
  br i1 %or.cond, label %.split.us.1, label %37

37:                                               ; preds = %.split.us.preheader
  %38 = icmp ne i32 %34, 0
  %39 = zext i1 %38 to i64
  %40 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %indvars.iv63, i64 %39
  %41 = load i64, ptr %40, align 8, !tbaa !3
  %42 = load i64, ptr %35, align 8, !tbaa !3
  %43 = add i64 %42, %41
  store i64 %43, ptr %40, align 8, !tbaa !3
  br label %.split.us.1

.split.us.1:                                      ; preds = %37, %.split.us.preheader
  %.not45.us.1 = icmp sle i64 %32, %indvars.iv63
  %44 = icmp slt i32 %34, 1
  %or.cond.1 = select i1 %.not45.us.1, i1 true, i1 %44
  br i1 %or.cond.1, label %.split.us.2, label %45

45:                                               ; preds = %.split.us.1
  %46 = icmp ugt i32 %34, 1
  %47 = zext i1 %46 to i64
  %48 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %47
  %49 = load i64, ptr %48, align 8, !tbaa !3
  %50 = load i64, ptr %35, align 8, !tbaa !3
  %51 = add i64 %50, %49
  store i64 %51, ptr %48, align 8, !tbaa !3
  br label %.split.us.2

.split.us.2:                                      ; preds = %45, %.split.us.1
  %52 = icmp slt i32 %34, 2
  %or.cond.2 = select i1 %.not45.us.1, i1 true, i1 %52
  br i1 %or.cond.2, label %.split.us.3, label %53

53:                                               ; preds = %.split.us.2
  %54 = icmp ugt i32 %34, 2
  %55 = zext i1 %54 to i64
  %56 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %55
  %57 = load i64, ptr %56, align 8, !tbaa !3
  %58 = load i64, ptr %35, align 8, !tbaa !3
  %59 = add i64 %58, %57
  store i64 %59, ptr %56, align 8, !tbaa !3
  br label %.split.us.3

.split.us.3:                                      ; preds = %53, %.split.us.2
  %60 = icmp slt i32 %34, 3
  %or.cond.3 = select i1 %.not45.us.1, i1 true, i1 %60
  br i1 %or.cond.3, label %.split.us.4, label %61

61:                                               ; preds = %.split.us.3
  %62 = icmp ugt i32 %34, 3
  %63 = zext i1 %62 to i64
  %64 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %63
  %65 = load i64, ptr %64, align 8, !tbaa !3
  %66 = load i64, ptr %35, align 8, !tbaa !3
  %67 = add i64 %66, %65
  store i64 %67, ptr %64, align 8, !tbaa !3
  br label %.split.us.4

.split.us.4:                                      ; preds = %61, %.split.us.3
  %68 = icmp slt i32 %34, 4
  %or.cond.4 = select i1 %.not45.us.1, i1 true, i1 %68
  br i1 %or.cond.4, label %.split.us.5, label %69

69:                                               ; preds = %.split.us.4
  %70 = icmp ugt i32 %34, 4
  %71 = zext i1 %70 to i64
  %72 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %71
  %73 = load i64, ptr %72, align 8, !tbaa !3
  %74 = load i64, ptr %35, align 8, !tbaa !3
  %75 = add i64 %74, %73
  store i64 %75, ptr %72, align 8, !tbaa !3
  br label %.split.us.5

.split.us.5:                                      ; preds = %69, %.split.us.4
  %76 = icmp slt i32 %34, 5
  %or.cond.5 = select i1 %.not45.us.1, i1 true, i1 %76
  br i1 %or.cond.5, label %.split.us.6, label %77

77:                                               ; preds = %.split.us.5
  %78 = icmp ugt i32 %34, 5
  %79 = zext i1 %78 to i64
  %80 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %79
  %81 = load i64, ptr %80, align 8, !tbaa !3
  %82 = load i64, ptr %35, align 8, !tbaa !3
  %83 = add i64 %82, %81
  store i64 %83, ptr %80, align 8, !tbaa !3
  br label %.split.us.6

.split.us.6:                                      ; preds = %77, %.split.us.5
  %84 = icmp slt i32 %34, 6
  %or.cond.6 = select i1 %.not45.us.1, i1 true, i1 %84
  br i1 %or.cond.6, label %.split.us.7, label %85

85:                                               ; preds = %.split.us.6
  %86 = icmp ugt i32 %34, 6
  %87 = zext i1 %86 to i64
  %88 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %87
  %89 = load i64, ptr %88, align 8, !tbaa !3
  %90 = load i64, ptr %35, align 8, !tbaa !3
  %91 = add i64 %90, %89
  store i64 %91, ptr %88, align 8, !tbaa !3
  br label %.split.us.7

.split.us.7:                                      ; preds = %85, %.split.us.6
  %92 = icmp slt i32 %34, 7
  %or.cond.7 = select i1 %.not45.us.1, i1 true, i1 %92
  br i1 %or.cond.7, label %.split.us.8, label %93

93:                                               ; preds = %.split.us.7
  %94 = icmp ugt i32 %34, 7
  %95 = zext i1 %94 to i64
  %96 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %95
  %97 = load i64, ptr %96, align 8, !tbaa !3
  %98 = load i64, ptr %35, align 8, !tbaa !3
  %99 = add i64 %98, %97
  store i64 %99, ptr %96, align 8, !tbaa !3
  br label %.split.us.8

.split.us.8:                                      ; preds = %93, %.split.us.7
  %100 = icmp slt i32 %34, 8
  %or.cond.8 = select i1 %.not45.us.1, i1 true, i1 %100
  br i1 %or.cond.8, label %.split.us.9, label %101

101:                                              ; preds = %.split.us.8
  %102 = icmp ugt i32 %34, 8
  %103 = zext i1 %102 to i64
  %104 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %103
  %105 = load i64, ptr %104, align 8, !tbaa !3
  %106 = load i64, ptr %35, align 8, !tbaa !3
  %107 = add i64 %106, %105
  store i64 %107, ptr %104, align 8, !tbaa !3
  br label %.split.us.9

.split.us.9:                                      ; preds = %101, %.split.us.8
  %108 = icmp slt i32 %34, 9
  %or.cond.9 = select i1 %.not45.us.1, i1 true, i1 %108
  br i1 %or.cond.9, label %.split53.us, label %109

109:                                              ; preds = %.split.us.9
  %110 = icmp ugt i32 %34, 9
  %111 = zext i1 %110 to i64
  %112 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %27, i64 %111
  br label %.split53.us.sink.split

.split:                                           ; preds = %28
  br i1 %.not45.us, label %118, label %113

113:                                              ; preds = %.split
  %114 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %indvars.iv63, i64 %indvars.iv
  %115 = load i64, ptr %114, align 8, !tbaa !3
  %116 = load i64, ptr %35, align 8, !tbaa !3
  %117 = add i64 %116, %115
  store i64 %117, ptr %114, align 8, !tbaa !3
  br label %118

118:                                              ; preds = %113, %.split
  %.not45.1.not = icmp sgt i64 %32, %indvars.iv63
  br i1 %.not45.1.not, label %119, label %.split53.us

119:                                              ; preds = %118
  %120 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %26, i64 %indvars.iv
  %121 = load i64, ptr %120, align 8, !tbaa !3
  %122 = load i64, ptr %35, align 8, !tbaa !3
  %reass.add = shl i64 %122, 1
  %123 = add i64 %121, %reass.add
  %124 = add i64 %122, %123
  %reass.add102 = shl i64 %122, 1
  %125 = add i64 %124, %reass.add102
  %126 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %26, i64 %indvars.iv
  %127 = add i64 %122, %125
  store i64 %127, ptr %126, align 8, !tbaa !3
  %128 = load i64, ptr %35, align 8, !tbaa !3
  %129 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %26, i64 %indvars.iv
  %reass.add103 = shl i64 %128, 1
  %130 = add i64 %127, %reass.add103
  store i64 %130, ptr %129, align 8, !tbaa !3
  %131 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %23, i64 %26, i64 %indvars.iv
  br label %.split53.us.sink.split

.split53.us.sink.split:                           ; preds = %109, %119
  %.sink = phi ptr [ %131, %119 ], [ %112, %109 ]
  %132 = load i64, ptr %.sink, align 8, !tbaa !3
  %133 = load i64, ptr %35, align 8, !tbaa !3
  %134 = add i64 %133, %132
  store i64 %134, ptr %.sink, align 8, !tbaa !3
  br label %.split53.us

.split53.us:                                      ; preds = %.split53.us.sink.split, %118, %.split.us.9
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, 2
  br i1 %exitcond.not, label %135, label %28

135:                                              ; preds = %.split53.us
  %indvars.iv.next64 = add nuw nsw i64 %indvars.iv63, 1
  %exitcond84.not = icmp eq i64 %indvars.iv.next64, 4
  br i1 %exitcond84.not, label %136, label %.preheader

136:                                              ; preds = %135
  %exitcond88.not = icmp eq i64 %indvars.iv.next86, %wide.trip.count
  br i1 %exitcond88.not, label %._crit_edge, label %.preheader47

._crit_edge:                                      ; preds = %136, %.._crit_edge_crit_edge
  %137 = phi i64 [ %.pre, %.._crit_edge_crit_edge ], [ %32, %136 ]
  %138 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %20, i64 %137, i64 0
  %139 = load i64, ptr %138, align 16, !tbaa !3
  %140 = getelementptr [106 x [4 x [2 x i64]]], ptr @_QFEdp, i64 0, i64 %20, i64 %137, i64 1
  %141 = load i64, ptr %140, align 8, !tbaa !3
  %142 = add i64 %141, %139
  %143 = trunc i64 %142 to i32
  store i32 %143, ptr @_QFEans, align 4, !tbaa !3
  %144 = call ptr @_FortranAioBeginExternalListOutput(i32 -1, ptr nonnull @_QQcl.dc03768eea24ae936d9c97250a8c3b66, i32 38)
  %145 = load i32, ptr @_QFEans, align 4, !tbaa !3
  %146 = call i1 @_FortranAioOutputInteger32(ptr %144, i32 %145)
  %147 = call i32 @_FortranAioEndIoStatement(ptr %144)
  ret void
}

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

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

declare i32 @_FortranAioEndIoStatement(ptr) local_unnamed_addr

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

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

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

declare i1 @_FortranAioOutputInteger32(ptr, i32) local_unnamed_addr

!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"}
