class IpAddresses
{
  public:
    int dp[105][105];
    string n;
    int k;
    bool cmp(string A, string B) {
        if(A.size() > B.size()) {
            return false;
        }
        if(A.size() < B.size()) {
            return true;
        }
        if(A < B) {
            return true;
        }
        if(A == B) {
            return true;
        }
        return false;
    }
    int rec(int i, int br) {
        if(i == n.size() - 1 and k == br) {
            return 1;
        }
        if(i != -1 and dp[i][br] != -1) {
            return dp[i][br];
        }
        int result = 0;
        string tmp = "";
        for(int j = i + 1; j < n.size(); j++) {
            tmp += n[j];
            if(tmp.size() >= 2 and tmp[0] == '0') {
                continue;
            }
            if(cmp(tmp, "255")) {
                result += rec(j, br + 1);
                result %= 1000000007;
            }
            else {
                break;
            }
            
        }
        return dp[i][br] = result;
    }
    int count( string S, int K )
    {
        n = S;
        k = K;
        memset(dp, -1, sizeof dp);
        return rec(-1, 0);
     
    }
};