400

import java.util.HashMap;

public class IpAddresses {
    public static HashMap<State, Integer> memo;
    public static int MOD;

    public static int solve(String S, int K){
        State key = new State(S, K);
        Integer m = memo.get(key);
        if(m != null){
            //System.out.println("MEMO");
            return m;
        }

        int len = S.length();
        if(K == 0){
            if(len == 0){
                memo.put(key, 1);
                return 1;
            }
            else{
                memo.put(key, 0);
                return 0;
            }
        }

        int sum = 0;

        //ednocifren
        if(len > 0){
            sum += solve(S.substring(1), K - 1);
            sum %= MOD;
        }

        //dvocifren
        if(len > 1 && S.charAt(0) != '0'){
            sum += solve(S.substring(2), K - 1);
            sum %= MOD;
        }

        //trocifren
        if(len > 2 && S.charAt(0) != '0' && Integer.parseInt(S.substring(0, 3)) < 256){
            sum += solve(S.substring(3), K - 1);
            sum %= MOD;
        }

        memo.put(key, sum);
        return sum;
    }

    public static int count(String S, int K) {
        MOD = 1000000007;
        memo = new HashMap<>();
        return solve(S, K);
    }

//  public static void main(String[] args) {
//      System.out.println(count("1234567", 3));
//  }
}

class State{
    String S;
    int K;
    State(String ss, int KK){
        S = ss;
        K = KK;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + K;
        result = prime * result + ((S == null) ? 0 : S.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        State s = (State) obj;
        return K == s.K && S.equals(s.S);
    }
}