【競プロ典型 90 問】 005 - Restricted Digits（★7） https://atcoder.jp/contests/typical90/tasks/typical90_e

005.cpp

#include <bits/stdc++.h>
using namespace std;
using LL = long long int;

#define inc(i, n) for(int i = 0; i < (n); i++)

const int MOD = 1'000'000'007;
int b;
struct S {
	vector<LL> v;
	int w;
	S(int ww) : v(b), w(ww % b) { }
	friend void operator*=(S & x, S const & y) {
		S ans(x.w * y.w);
		inc(i, b) {
		inc(j, b) {
			(ans.v[(y.w * i + j) % b] += x.v[i] * y.v[j]) %= MOD;
		}
		}
		x = ans;
	}
};

LL ri() { LL a; cin >> a; return a; }
LL bit(LL n, LL i) { return (n >> i) & 1; }

int main() {
	LL n = ri();
	cin >> b;
	S ans(1), ex(10);
	ans.v[0] = 1;
	{
		int k = ri();
		inc(i, k) { ex.v[ri() % b]++; }
	}
	
	inc(i, 60) {
		if(bit(n, i) == 1) { ans *= ex; }
		ex *= ex;
	}
	cout << ans.v[0] << endl;
}