分饼干

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {

            String s = in.nextLine();

            String s2 = in.nextLine();

            int n = Integer.parseInt(s2);

            long d[] = new long[n];//n children

            boolean dLoaded = false;

            long base = 1;

            long sum = 0;

            for (int j = 0; j < s.length(); j++) {

                base *= 10;

            }

        //遍历每一位数字。

            for (int i = 0; i < s.length(); i++) {

        //对base除以10，为下一位求余做准备。

                base /= 10;

                if (s.charAt(i) == 'X') {

                    if (!dLoaded) {

                    //如果记录余数的数组d还没初始化过，就先把这次的计算作为初始化的值。

                        long[] temp = new long[n];

                        //统计余数的数组。长度为n，下标是0~n-1，表示 对应可以得到对应余数的个数。

                        for (int j = 0; j <= 9; j++) {

                            temp[(int) ((j * base) % n)]++;

                        }

                           //temp数组复制到d数组上。这里idea优化成如下方法，效率更高。d数组便初始化过了。跳过后面部分

                        System.arraycopy(temp, 0, d, 0, n);

                        dLoaded = true;

                        continue;

                    }

                    //如果初始化了d数组，则在新发现X时，需要把新的余数统计结果和原来的统计结果d进行汇总

                    int[] mod = new int[10];

                        //因为x有10种可能，所以最多产生10个余数，而如果采用new int[n]来统计的话，n可能远大于10，所以效率会差很多。mod记录了每个可能的数字所产生的余数。

                    for (int j = 0; j <= 9; j++) {

                        mod[j] = (int) ((j * base) % n);

                    }

                    //将新的统计结果mod和原来的统计结果d进行融合。原理如下：newd的下标对应产生的余数，比如newd[2]代表余数为2的所有可能性总数。于是对于newd[m]，其可能性总数便来自于 sum{d[m-mod[k]]}（仔细想一下，mod[k]是这次产生的新余数，m是要统计的目标余数），+n和%n是为了防止负数情况。

                    long[] newd = new long[n];

                    for (int m = 0; m < n; m++) {

                        for (int k = 0; k <= 9; k++) {

                            newd[m] += d[(n + m - mod[k]) % n];

                        }

                    }

                    System.arraycopy(newd, 0, d, 0, n);

                } else {

                //如果不是x，就按最开始处讲的原理直接求余并累加进去即可。

                    long a = (s.charAt(i) - '0') * base;

                    sum = (sum + a) % n;

                }

            }

            //常数位累加后的余数是sum，而我们要能整除的所有可能性，也就是余数为0的所有可能性，所以取d数组中的n-sum对应的可能性即可。为何%n?比如n=7，sum=0，n-sum=7，d[7]显然越界。实际上此时应该去访问d[7%7]=d[0]

            System.out.println(d[(int) ((n - sum) % n)]);

        }

    }

}