You are given two integers l and r (l ≤ r). Your task is to calculate the sum of numbers from l to r (including l and r) such that each number contains at most k different digits, and print this sum modulo 998244353.

For example, if k = 1 then you have to calculate all numbers from l to r such that each number is formed using only one digit. For l = 10, r = 50 the answer is 11 + 22 + 33 + 44 = 110.

Input

The only line of the input contains three integers l, r and k (1 ≤ l ≤ r < 10^{18}, 1 ≤ k ≤ 10) — the borders of the segment and the maximum number of different digits.

Output

Print one integer — the sum of numbers from l to r such that each number contains at most k different digits, modulo 998244353.

Examples

Input

10 50 2


Output

1230


Input

1 2345 10


Output

2750685


Input

101 154 2


Output

2189

Note

For the first example the answer is just the sum of numbers from l to r which equals to (50 ⋅ 51)/(2) - (9 ⋅ 10)/(2) = 1230. This example also explained in the problem statement but for k = 1.

For the second example the answer is just the sum of numbers from l to r which equals to (2345 ⋅ 2346)/(2) = 2750685.

For the third example the answer is 101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189.
/**
 * BaZ :D
 */
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Main
{
    static Reader scan;
    static PrintWriter pw;
    static int dig[] = new int[19];
    static long ten[] = new long[19];
    static int k;
    static long MOD = 998244353;
    static Pair dp[][][][];
    public static void main(String[] args) {
        new Thread(null,null,"BaZ",1<<25)
        {
            public void run()
            {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
    static void solve() throws IOException
    {
        scan = new Reader();
        pw = new PrintWriter(System.out,true);
        StringBuilder sb = new StringBuilder();
        ten[0]++;
        for(int i=1;i<19;++i) {
            ten[i] = 10*ten[i-1];
            ten[i]%=MOD;
        }
        long L = nl(), R = nl();
        k = ni();
        Pair foo = calc(R);
        Pair bar = calc(L-1);
        long ans = foo.x - bar.x + MOD;
        ans%=MOD;
        pl(ans);
        pw.flush();
        pw.close();
    }
    static Pair calc(long x) {
        int idx = 18;
        while(idx>=0) {
            dig[idx--] = (int)(x%10);
            x/=10;
        }
        dp = new Pair[19][1024][2][2];
        return f(0,0,0,0);
    }
    static Pair f(int idx, int mask, int already_smaller, int started) {
        if(idx==19) {
            return new Pair(0,1);
        }
        if(dp[idx][mask][already_smaller][started]!=null) {
            return dp[idx][mask][already_smaller][started];
        }
        if(already_smaller==1) {
            Pair lol = new Pair(0,0);
            if(started==0) {
                //can append 0 anyways without affecting mask
                lol.add(f(idx+1, mask, 1, 0));
            }
            else {
                //can append 0, but it will affect mask
                if(isSafe(mask, 0)) {
                    lol.add(f(idx+1, mask|1, 1, 1));
                }
            }
            for(int i=1;i<10;++i) {
                if(isSafe(mask, i)) {
                    Pair nex = f(idx+1, mask|(1<<i), 1,1);
                    lol.add(nex);
                    long iska_contri = 1L*i*ten[18-idx];
                    iska_contri%=MOD;
                    iska_contri*=nex.y;
                    iska_contri%=MOD;
                    lol.x = (lol.x + iska_contri)%MOD;
                }
            }
            return dp[idx][mask][already_smaller][started] = lol;
        }
        else {
            Pair lol = new Pair(0,0);
            if(started==0) {
                //can append 0 anyways without affecting mask
                lol.add(f(idx+1, mask, dig[idx]>0?1:0, started));
            }
            else {
                if(isSafe(mask, 0)) {
                    lol.add(f(idx+1, mask|1, dig[idx]>0?1:0, started));
                }
            }
            for(int i=1;i<dig[idx];++i) {
                if(isSafe(mask, i)) {
                    Pair nex = f(idx+1, mask|(1<<i), 1, 1);
                    lol.add(nex);
                    long iska_contri = 1L*i*ten[18-idx];
                    iska_contri%=MOD;
                    iska_contri*=nex.y;
                    iska_contri%=MOD;
                    lol.x = (lol.x + iska_contri)%MOD;
                }
            }
            if(dig[idx]>0 && isSafe(mask, dig[idx])) {
                Pair nex = f(idx+1, mask|(1<<dig[idx]), 0, 1);
                lol.add(nex);
                long iska_contri = dig[idx]*ten[18-idx];
                iska_contri%=MOD;
                iska_contri*=nex.y;
                iska_contri%=MOD;
                lol.x = (lol.x + iska_contri)%MOD;
            }
            return dp[idx][mask][already_smaller][started] = lol;
        }
    }
    static boolean isSafe(int mask, int dig) {
        return Integer.bitCount((mask|(1<<dig)))<=k;
    }
    static class Pair {
        long x,y;
        Pair(long x, long y) {
            this.x=x;
            this.y=y;
        }
        public void add(Pair p) {
            this.x+=p.x;
            this.y+=p.y;
            if(this.x>=MOD) {
                this.x-=MOD;
            }
            if(this.y>=MOD) {
                this.y-=MOD;
            }
        }
        public String toString() {
            return "{"+x+","+y+"}";
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
}