class Solution {
    String s;
    int dp[][];
    public int atMostNGivenDigitSet(String[] A, int n) {
        s=n+"";
        int res=0;
        for(int i=1;i<s.length();i++){
            int pro=1;
            for(int j=0;j<i;j++){
                pro*=A.length;
            }
            res+=pro;
        }
        dp=new int[s.length()][2];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        int cnt=dfs(A,0,1);
        return res+cnt;
    }
    
    
    //only for length N
    public int dfs(String A[],int index,int state){//0:same prefix   1:different
        if(index>=s.length())return 1;
        if(dp[index][state]!=-1)return dp[index][state];
        int res=0;
        for(int i=0;i<A.length;i++){
            int d=Integer.parseInt(A[i]);
            if(state==1){
                if(d<(s.charAt(index)-'0')){
                    res+=dfs(A,index+1,0);
                }
                if(d==(s.charAt(index)-'0')){
                    res+=dfs(A,index+1,1);
                }
            }else{
                res+=dfs(A,index+1,state);
            }
        }
        dp[index][state]=res;
        return res;
    }
}