如果两个只包含数字且长度为 nn 的字符串 ss 和 ww 存在两个数字 1≤i,j≤n
使得 si<wi,sj>wj
则称 ss 和 ww 是不可比的。现在给定两个包含数字和问号且长度为 nn 的字符串，
问有多少种方案使得将所有问号替换成0到9的数字后两个字符串是不可比的
明显的容斥原理
但注意 a[i]==b[i]
TOTAL - ans1- ans2- ans3
// LUOGU_RID: 105563032
#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5+4;
#define int long long
const int mod= 1e9+7;
char a[N],b[N];
int n,f[N],g[N] ;
int T;
int Cnt=0;
int Pow(int x,int y){
if(y==0) return 1;
int t=Pow(x,y/2);
if(y&1) return ((t*t)%mod*x)%mod;
return (t*t)%mod;
}
signed main(){
int i,j;
cin>>n;
for(i=1;i<=n;++i){
cin>>a[i]; if(a[i]!='?') a[i]-='0';else Cnt++;
}
for(i=1;i<=n;++i){
cin>>b[i]; if(b[i]!='?') b[i]-='0';else Cnt++;
}
Cnt=Pow(10,Cnt) ;
f[0]=g[0]=1;
for(i=0;i<=9;i++)
for(j=0;j<=i;j++) T++;
for(i=1;i<=n;i++){
if(a[i]=='?'&&b[i]=='?') f[i]=f[i-1]*T;
else if(a[i]=='?'&&b[i]!='?')
f[i]=f[i-1]*(10-b[i]);
else if(a[i]!='?'&&b[i]=='?')
f[i]=f[i-1]*(1+a[i]);
else
f[i]=f[i-1]*(a[i]>=b[i]);
f[i]%=mod;
if(f[i]==0) break;
}
for(i=1;i<=n;i++){
if(a[i]=='?'&&b[i]=='?') g[i]=g[i-1]*T;
else if(a[i]=='?'&&b[i]!='?')
g[i]=g[i-1]*(1+b[i]);
else if(a[i]!='?'&&b[i]=='?')
g[i]=g[i-1]*(10-a[i]);
else
g[i]=g[i-1]*(a[i]<=b[i]);
g[i]%=mod;
if(g[i]==0) break;
}
int tmp =1;
for(i=1;i<=n&&tmp;i++){
if(a[i]=='?'&&b[i]=='?') tmp*=10;
else if(a[i]=='?'&&b[i]!='?')
;
else if(a[i]!='?'&&b[i]=='?')
;
else tmp*=(a[i]==b[i]);
tmp%=mod;
if(tmp==0) break;
}
cout<<( (Cnt-f[n]-g[n]+tmp)%mod+mod)%mod <<endl;
}