记录
代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x){
	x=0;bool f=0;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-')f=1;
		ch=getchar();
	}do{x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}while(ch>='0'&&ch<='9');
	x=f?-x:x;
}
int p,dp[1000001],a[1000001],sum;
string s;
signed main(){
	read(p),cin>>s;
	for(int i=0;i<p;i++)a[i]=0;
	for(int i=0;i<s.size();i++){
		for(int j=0;j<p;j++)dp[j]=0;
		int d=s[i]-48;
		for(int j=0;j<p;j++)dp[(d+j*10)%p]+=a[j];
		dp[d%p]++,sum+=dp[0];
		for(int j=0;j<p;j++)a[j]=dp[j];
	}cout<<sum;
	return 0;
}