local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end

local DBG = false

local function dbgpr(...)
    if DBG then
        io.write("[dbg]")
        print(...)
    end
end

local function dbgpr_t(tbl, use_pairs)
    if DBG then
        local enum = ipairs
        if use_pairs then
            enum = pairs
        end
        dbgpr(tbl)
        io.write("[dbg]")
        for i,v in enum(tbl) do
            io.write(i)
            io.write(":")
            io.write(tostring(v))
            io.write(" ")
        end
        print("")
    end
end

local function dbgpr_tp(tbl)
    dbgpr_t(tbl, true)
end

----
local function factorial(n)
    local a = 1
    for i=1, n do
        a = a * i
    end
    return a
end

local function nCr(n, r)
    if r > n then
        return 0
    end
    if r > n/2 then
        r = n - r
    end
    local a = 1
    for i=n, n-r+1, -1 do
        a = a * i
    end
    return a // factorial(r)
end


local function normal(d, k)
    dbgpr("normal d,k ", d, k)
    return nCr(d, k) * math.floor(9^k)
end

-- E
local tmp = read.l():totable()
local N = {}
for i=1,#tmp do
    N[i] = tonumber(tmp[i])
end
local D = #N
local K = read.n()

local x = 1
local ans1, ans2, ans3, ans4, ans5, ans6 = 0, 0, 0, 0, 0, 0
if K == 1 then
    ans1 = normal(D-1, K)
    ans2 = N[1]
elseif K == 2 then
    ans1 = normal(D-1, K)
    ans2 = (N[1] - 1) * normal(D-1, K-1)
    x = 2
    local found = false
    for i=x,D do
        if N[i] ~= 0 then
            x = i
            found = true
            break
        end
    end
    if found then
        if x == D then
            ans4 = N[x]
        else
            ans3 = normal(D-x, K-1)
            ans4 = N[x]
        end
    end
elseif K == 3 then
    ans1 = normal(D-1, K)
    ans2 = (N[1] - 1) * normal(D-1, K-1)
    x = 2
    local found = false
    for i=x,D do
        if N[i] ~= 0 then
            x = i
            found = true
            break
        end
    end
    if found then
        if x == D then
        else
            ans3 = normal(D-x, K-1)
            ans4 = (N[x] - 1) * normal(D-x, K-2)
            x = x + 1
            found = false
            for i=x,D do
                if N[i] ~= 0 then
                    x = i
                    found = true
                    break
                end
            end
            if found then
                if x == D then
                    ans6 = N[x]
                else
                    ans5 = normal(D-x, K-2)
                    ans6 = N[x]
                end
            end
        end
    end
end
dbgpr("ans1", ans1)
dbgpr("ans2", ans2)
dbgpr("ans3", ans3)
dbgpr("ans4", ans4)
dbgpr("ans5", ans5)
dbgpr("ans6", ans6)

print(ans1+ans2+ans3+ans4+ans5+ans6)

Measured memory_bytes: 888