class Result {

    /*
     * Complete the 'wordBreakCount' function below.
     *
     * The function accepts STRING_ARRAY dictionary as parameter and the original
     * string txt on which segmentation is to be performed. The function returns the
     * count of all possible segmentation arrangements.
     */

    public static void helper(int idx, String txt, List<String> dict, int[] dp){
        if(idx == txt.length()){
            return;
        }
        for(String word: dict){
            int cSize = word.length();
            if(idx+cSize > txt.length() || !word.equals(txt.substring(idx, idx+cSize))){
                continue;
            }
            dp[idx+cSize-1] += (idx==0)?1:dp[idx-1];
            dp[idx+cSize-1] %= 1000000007;
        }
        helper(idx+1, txt, dict, dp);
    }

    public static int wordBreakCount(List<String> dictionary, String txt) {
        // Write your code here
        int[] dp = new int[txt.length()+1];
        Arrays.fill(dp, 0);
        helper(0, txt, dictionary, dp);
        return dp[txt.length()-1];
    }

}