#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector < pair<int,int> > sums; //to store all possible sums with how many letter they took
vector <int> letters;
//function for backtracking all sums
void solve(int pos, int sum, int cnt){
	if(pos==letters.size()-1){
		if(sum!=0) sums.push_back({cnt,sum});
		sums.push_back({cnt+1,sum+letters[pos]});
	}
	else{
		solve(pos+1,sum,cnt);
		solve(pos+1,sum+letters[pos],cnt+1);
	}
}
int main(){
	string x;
	cin>>x;
	int p;
	cin>>p;
	for(int i=0 ; i<x.size() ; i++){
		letters.push_back(x[i]);
	}
	solve(0,0,0);
	long long ans=0;
	for(int i=0 ; i<sums.size() ; i++){
		if(sums[i].second%p==0){
			long long y=1;
			for(int j=1 ; j<=sums[i].first ; j++){
				y=(y*j)%(1000000007);
			}
			ans=(ans+y)%(1000000007);
		}
	}
	cout<<ans<<endl;
	return 0;
}