HackerRank Hyper Strings Problem Solution

In this post, we will solve HackerRank Hyper Strings Problem Solution.

String A is called a Super String if and only if:

A contains only letters a, b, c, d, e, f, g, h, i, j;
For any i and j. A[i] has lower ascii code than A[j], where 0 < i < j < length (A)
Given a set of Super Strings H. a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set H. We can use each Super String as many times as we want.
Given set H. you have to compute the number of Hyper Strings with length no greater than
M.
Input Format
The first line of input contains two integers, N (the number of Super Strings in H) and M. The next N lines describe the Super Strings in set H.
Constraints
N and M are not greater than 100.
Output Format
Output an integer which is the number of possible Hyper Strings that can be derived. Since it may not fit in 32 bit integer, print the output module 1000000007. (i.e. answer = answer
% 1000000007)

Sample Input

2 3  
a  
ab

Sample Output

Explanation

In the example all the Hyper Strings are : “” (empty string), “a”, “ab”, “aaa”, “aa”, “aba”, and “aab”.

Table of Contents

Hyper Strings C Solution

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char* readline();
char** split_string(char*, int*);

/*
 * Complete the hyperStrings function below.
 */
int hyperStrings(int m, int n, char** H) {
    int basicmasks[n];
    int low[n];
    for(int i = 0; i < n; i++){
        basicmasks[i] = 0;
        low[i] = H[i][0] - 'a';
        int len = strlen(H[i]);
        for(int j = 0; j < len; j++){
            basicmasks[i] += 1<<(H[i][j] - 'a');
        }
    }

    int masks[1024];
    int masklow[1024];
    int maskhigh[1024];
    int maskbits[1024];
    masks[0] = 1;
    for(int i = 1; i < 1024; i++){
        masks[i] = 0;
        for(int j = 0; j < n; j++){
            if((i&basicmasks[j]) == basicmasks[j] && (i - basicmasks[j]) < (1<<low[j]) && masks[i - basicmasks[j]] == 1){
                masks[i] = 1;
            }
        }
        maskhigh[i] = -1;
        masklow[i] = -1;
        maskbits[i] = 0;
        for(int j = 0; j < 10; j++){
            if(((i>>j)&1) == 1){
                maskhigh[i] = j;
                if(masklow[i] == -1){
                    masklow[i] = j;
                }
                maskbits[i]++;
            }
        }
    }

    int currnum[m + 1][10];
    for(int i = 0; i <= m; i++){
        for(int j = 0; j < 10; j++){
            currnum[i][j] = 0;
        }
    }
    currnum[0][9] = 1;

    for(int i = 1; i <= m; i++){
        for(int j = 1; j < 1024; j++){
            int prevlen = i - maskbits[j];
            if(masks[j] == 1 && prevlen >= 0){
                for(int k = masklow[j]; k < 10; k++){
                    currnum[i][maskhigh[j]] = (currnum[i][maskhigh[j]] + currnum[prevlen][k])%MOD;
                }
            }
        }
    }

    int total = 0;
    for(int i = 0; i <= m; i++){
        for(int j = 0; j < 10; j++){
            total = (total + currnum[i][j])%MOD;
        }
    }
    return total;

}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    int temp;
    char** nm = split_string(readline(), &temp);

    char* n_endptr;
    char* n_str = nm[0];
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    char* m_endptr;
    char* m_str = nm[1];
    int m = strtol(m_str, &m_endptr, 10);

    if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }

    char** H = malloc(n * sizeof(char*));

    for (int H_itr = 0; H_itr < n;) {
        int temp;
        char** itemlist = split_string(readline(), &temp);

        for(int i = 0; i < temp; i++){
            *(H + H_itr) = itemlist[i];
            H_itr++;
        }
    }

    int result = hyperStrings(m, n, H);

    fprintf(fptr, "%d\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }
    if(data[data_length - 1] != '\0'){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str, int* num) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }
    *num = spaces;

    return splits;
}

Hyper Strings C++ Solution

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>

using namespace std;
#define ll long long int 
vector<string> vs , distr;
map<string , int > mp;

void f( string s , int &N   ) {
    if( mp[s] ) return;
    mp[s] = 1;
    char ch = s[s.size()-1];
    for( int i = 0; i < N; i++ ) {    
        if( vs[i][0] > ch ) f( s+vs[i] , N );
    }
    distr.push_back(s);
}

long long int dp[200][12];
int DISTR;

long long int MOD = 1000000007;

long long int f1( int len , int lastchar ) {
    
    if( len <= 0 ) return 1;
    long long int &ret = dp[len][lastchar];
    if( ret == -1ll ) { 
        ret = 0ll;
        for( int i = 0; i < DISTR; i++ ) {
            int tsz = distr[i].size();
            int fs = distr[i][0]-'a' , ls = distr[i][tsz-1]-'a';
            if( (tsz <= len) &&  (fs) <= lastchar ) ret += f1( len-tsz , ls );
            ret %= MOD;
        }
    }
    return ret;
}
int main () {
    int N , L;mp.clear();
    scanf("%d %d" , &N , &L );    
    for( int i = 0; i < N; i++ ) {
        string s; cin >> s;
        vs.push_back(s);
    }
    
    f( "" , N );    
    int sz = distr.size()-1;    
    distr.resize(sz);DISTR = sz;

    sort( distr.begin()  , distr.end() );
/*    cout << DISTR << "\n";
    for( int i = 0; i < DISTR; i++ ) cout << distr[i] << "\n";
*/
    memset( dp , -1  , sizeof(dp) );        
    ll ans = 0;
    for( int i = 0; i <= L; i++ ) {
        ans += f1( i , 11 );
        ans %= MOD;
    }
    cout << ans << "\n";
 
    return 0;
}

Hyper Strings C Sharp Solution

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace CSharpParser
{
    public class Solution : SolutionBase
    {
        protected override void Solve()
        {
            int n, m;
            Next(out n);
            Next(out m);
            var s = NextArray<string>(n);
            var can = new bool[1024];
            foreach (var mask in s.Select(str => str.Aggregate(0, (current, c) => current | 1 << c - 'a')))
                can[mask] = true;
            var d = new int[11, 10, 10];
            for (var i = 1; i < 1024; i++)
            {
                if (!can[i])
                    for (var j = 1; (i >> j) != 0; j++)
                        can[i] |= can[i >> j << j] && can[i & ~-(1 << j)];
                if (!can[i]) continue;
                var v = new List<int>();
                for (var j = 0; j < 10; j++)
                    if ((i >> j & 1) != 0)
                        v.Add(j);
                d[v.Count, v[v.Count - 1], v[0]]++;
            }
            for (var i = 1; i <= 10; i++)
                for (var j = 0; j < 10; j++)
                    for (var k = 1; k < 10; k++)
                        d[i, j, k] += d[i, j, k - 1];
            var ans = new int[m + 1, 10];
            ans[0, 9] = 1;
            var res = 1;
            for (var i = 1; i <= m; i++)
                for (var j = 0; j < 10; j++)
                {
                    for (var k = 1; k <= 10 && k <= i; k++)
                        for (var l = 0; l < 10; l++)
                            ans[i, j] = (int) ((ans[i, j] + (long) ans[i - k, l]*d[k, j, l])%1000000007);
                    res = (res + ans[i, j])%1000000007;
                }
            PrintLine(res);
        }
    }

    public static class Algorithm
    {
        public static void Swap<T>(ref T a, ref T b)
        {
            var temp = a;
            a = b;
            b = temp;
        }

        public static T Max<T>(params T[] a)
        {
            var ans = a[0];
            var comp = Comparer<T>.Default;
            for (var i = 1; i < a.Length; i++) ans = comp.Compare(ans, a[i]) >= 0 ? ans : a[i];
            return ans;
        }

        public static T Min<T>(params T[] a)
        {
            var ans = a[0];
            var comp = Comparer<T>.Default;
            for (var i = 1; i < a.Length; i++) ans = comp.Compare(ans, a[i]) <= 0 ? ans : a[i];
            return ans;
        }

        public static void RandomShuffle<T>(IList<T> a, int index, int length)
        {
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            var last = index + length;
            if (last > a.Count) throw new ArgumentException();
            var rnd = new Random(DateTime.Now.Millisecond);
            for (var i = index + 1; i < last; i++)
            {
                var j = rnd.Next(index, i + 1);
                var t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }

        public static void RandomShuffle<T>(IList<T> a)
        {
            RandomShuffle(a, 0, a.Count);
        }

        public static bool NextPermutation<T>(IList<T> a, int index, int length, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            var last = index + length;
            if (last > a.Count) throw new ArgumentException();
            for (var i = last - 1; i > index; i--)
                if (compare(a[i], a[i - 1]) > 0)
                {
                    var j = i + 1;
                    for (; j < last; j++) if (compare(a[j], a[i - 1]) <= 0) break;
                    var t = a[i - 1];
                    a[i - 1] = a[j - 1];
                    a[j - 1] = t;
                    for (; i < last - 1; i++, last--)
                    {
                        t = a[i];
                        a[i] = a[last - 1];
                        a[last - 1] = t;
                    }
                    return true;
                }
            for (var i = index; i < last - 1; i++, last--)
            {
                var t = a[i];
                a[i] = a[last - 1];
                a[last - 1] = t;
            }
            return false;
        }

        public static bool NextPermutation<T>(IList<T> a, Comparison<T> compare = null)
        {
            return NextPermutation(a, 0, a.Count, compare);
        }

        public static bool PrevPermutation<T>(IList<T> a, int index, int length, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            var last = index + length;
            if (last > a.Count) throw new ArgumentException();
            for (var i = last - 1; i > index; i--)
                if (compare(a[i], a[i - 1]) < 0)
                {
                    var j = i + 1;
                    for (; j < last; j++) if (compare(a[j], a[i - 1]) >= 0) break;
                    var t = a[i - 1];
                    a[i - 1] = a[j - 1];
                    a[j - 1] = t;
                    for (; i < last - 1; i++, last--)
                    {
                        t = a[i];
                        a[i] = a[last - 1];
                        a[last - 1] = t;
                    }
                    return true;
                }
            for (var i = index; i < last - 1; i++, last--)
            {
                var t = a[i];
                a[i] = a[last - 1];
                a[last - 1] = t;
            }
            return false;
        }

        public static bool PrevPermutation<T>(IList<T> a, Comparison<T> compare = null)
        {
            return PrevPermutation(a, 0, a.Count, compare);
        }

        public static int LowerBound<T>(IList<T> a, int index, int length, T value, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            if (index + length > a.Count) throw new ArgumentException();
            var ans = index;
            var last = index + length;
            var p2 = 1;
            while (p2 <= length) p2 *= 2;
            for (p2 /= 2; p2 > 0; p2 /= 2) if (ans + p2 <= last && compare(a[ans + p2 - 1], value) < 0) ans += p2;
            return ans;
        }

        public static int LowerBound<T>(IList<T> a, T value, Comparison<T> compare = null)
        {
            return LowerBound(a, 0, a.Count, value, compare);
        }

        public static int UpperBound<T>(IList<T> a, int index, int length, T value, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            if (index + length > a.Count) throw new ArgumentException();
            var ans = index;
            var last = index + length;
            var p2 = 1;
            while (p2 <= length) p2 *= 2;
            for (p2 /= 2; p2 > 0; p2 /= 2) if (ans + p2 <= last && compare(a[ans + p2 - 1], value) <= 0) ans += p2;
            return ans;
        }

        public static int UpperBound<T>(IList<T> a, T value, Comparison<T> compare = null)
        {
            return UpperBound(a, 0, a.Count, value, compare);
        }

        public static void Fill<T>(this IList<T> array, T value) where T : struct
        {
            for (var i = 0; i < array.Count; i++)
                array[i] = value;
        }
    }

    public class InStream : IDisposable
    {
        protected readonly TextReader InputStream;
        private string[] _tokens;
        private int _pointer;

        private InStream(TextReader inputStream)
        {
            InputStream = inputStream;
        }

        public static InStream FromString(string str)
        {
            return new InStream(new StringReader(str));
        }

        public static InStream FromFile(string str)
        {
            return new InStream(new StreamReader(str));
        }

        public static InStream FromConsole()
        {
            return new InStream(Console.In);
        }

        public string NextLine()
        {
            try
            {
                return InputStream.ReadLine();
            }
            catch (Exception)
            {
                return null;
            }
        }

        private string NextString()
        {
            try
            {
                while (_tokens == null || _pointer >= _tokens.Length)
                {
                    _tokens = NextLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                    _pointer = 0;
                }
                return _tokens[_pointer++];
            }
            catch (Exception)
            {
                return null;
            }
        }

        public bool Next<T>(out T ans)
        {
            var str = NextString();
            if (str == null)
            {
                ans = default(T);
                return false;
            }
            ans = (T)Convert.ChangeType(str, typeof(T));
            return true;
        }

        public T[] NextArray<T>(int length)
        {
            var array = new T[length];
            for (var i = 0; i < length; i++)
                if (!Next(out array[i]))
                    return null;
            return array;
        }

        public T[,] NextArray<T>(int length, int width)
        {
            var array = new T[length, width];
            for (var i = 0; i < length; i++)
                for (var j = 0; j < width; j++)
                    if (!Next(out array[i, j]))
                        return null;
            return array;
        }

        public void Dispose()
        {
            InputStream.Close();
        }
    }

    public class OutStream : IDisposable
    {
        protected readonly TextWriter OutputStream;

        private OutStream(TextWriter outputStream)
        {
            OutputStream = outputStream;
        }

        public static OutStream FromString(System.Text.StringBuilder strB)
        {
            return new OutStream(new StringWriter(strB));
        }

        public static OutStream FromFile(string str)
        {
            return new OutStream(new StreamWriter(str));
        }

        public static OutStream FromConsole()
        {
            return new OutStream(Console.Out);
        }

        public void Print(string format, params object[] args)
        {
            OutputStream.Write(format, args);
        }

        public void PrintLine(string format, params object[] args)
        {
            Print(format, args);
            OutputStream.WriteLine();
        }

        public void PrintLine()
        {
            OutputStream.WriteLine();
        }

        public void Print<T>(T o)
        {
            OutputStream.Write(o);
        }

        public void PrintLine<T>(T o)
        {
            OutputStream.WriteLine(o);
        }

        public void PrintArray<T>(IList<T> a, string between = " ", string after = "\n", bool printCount = false)
        {
            if (printCount)
                PrintLine(a.Count);
            for (var i = 0; i < a.Count; i++)
                Print("{0}{1}", a[i], i == a.Count - 1 ? after : between);
        }

        public void Dispose()
        {
            OutputStream.Close();
        }
    }

    public abstract class SolutionBase : IDisposable
    {
        private readonly InStream _in;
        private readonly OutStream _out;

        protected SolutionBase()
        {
            //System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture;
            _in = InStream.FromConsole();
            _out = OutStream.FromConsole();
        }

        protected string NextLine()
        {
            return _in.NextLine();
        }

        protected bool Next<T>(out T ans)
        {
            return _in.Next(out ans);
        }

        protected T[] NextArray<T>(int length)
        {
            return _in.NextArray<T>(length);
        }

        protected T[,] NextArray<T>(int length, int width)
        {
            return _in.NextArray<T>(length, width);
        }

        protected void PrintArray<T>(IList<T> a, string between = " ", string after = "\n", bool printCount = false)
        {
            _out.PrintArray(a, between, after, printCount);
        }

        public void Print(string format, params object[] args)
        {
            _out.Print(format, args);
        }

        public void PrintLine(string format, params object[] args)
        {
            _out.PrintLine(format, args);
        }

        public void PrintLine()
        {
            _out.PrintLine();
        }

        public void Print<T>(T o)
        {
            _out.Print(o);
        }

        public void PrintLine<T>(T o)
        {
            _out.PrintLine(o);
        }

        public void Dispose()
        {
            _out.Dispose();
        }

        protected abstract void Solve();

        public static void Main()
        {
            using (var p = new Solution()) p.Solve();
        }
    }
}

Hyper Strings Java Solution

// This solution is from https://programs.programmingoneonone.com/2021/07/hackerrank-hyper-strings-problem-solution.html 
// this is to check the quality of the question and the validity of the editorial.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

  static final int AB = 10;
  static final int MAX = 1 << AB;
  static final long MOD = 1_000_000_007;

  static long hyperStrings(int m, int[] arr) {
    Arrays.sort(arr);
    boolean[] b = new boolean[MAX];
    b[0] = true;
    for (int i = 0; i < arr.length; i++) {
      int n = 1 << Integer.numberOfTrailingZeros(arr[i]);
      for (int j = n-1; j >= 0; j--) {
        if (b[j]) {
          b[j | arr[i]] = true;
        }
      }
    }
    int[] a = new int[MAX];
    int n = 0;
    for (int i = 0; i < MAX; i++) {
      if (b[i]) {
          a[n++] = i;
      }
    }
  
    long result = 0;

    int[][] s = new int[a.length+1][AB];
    s[0][AB-1] = 1;
    for (int i = 0; i < m+1; i++) {
      for (int j = 0; j < AB; j++) {
        result = (result + s[i][j]) % MOD;
        for (int k = 0; k < n; k++) {
          int pop = Integer.bitCount(a[k]);
          int atz = Integer.numberOfTrailingZeros(a[k]);
          if ((i + pop) <= m && atz <= j) {
            int alz = Integer.numberOfLeadingZeros(a[k]);
            s[i+pop][31 - alz] = (int)((s[i+pop][31 - alz] + s[i][j]) % MOD);
          }
        }
      }
    }
    return result;
  }

  static void load(int[] a, int i, char[] arr) {
    for (char c : arr) {
        a[i] |= 1 << (c - 'a');
    }    
  }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] a = new int[n];
        String s = br.readLine();
        if (s.contains(" ")) {
          String[] v = s.split(" ");
          for (int i = 0; i < n; i++) {
            load(a, i, v[i].toCharArray());
          }
        } else {
          load(a, 0, s.toCharArray());
          for (int i = 1; i < n; i++) {
            load(a, i, br.readLine().toCharArray());
          }
        }

        long result = hyperStrings(m, a);

        bw.write(String.valueOf(result));
        bw.newLine();

        br.close();
        bw.close();
    }
}

Hyper Strings JavaScript Solution

function processData(input) {
    //Enter your code here
    var x={a:1,b:2,c:4,d:8,e:16,f:32,g:64,h:128,i:256,j:512};
    var z={a:1,b:2,c:3,d:4,e:5,f:6,g:7,h:8,i:9,j:10};
    var t=1000000007;
    var a = input.split("\n");
    var a2 = a[0].split(' ').map(Number);
    var n = a2[0], m=a2[1];
    var h = [], f = [];
    for (var i=0;i<=10;i++) {
        h[i]=[];
        for (var j=0;j<=11;j++) h[i][j] = 0;
    }
    for (var i=0;i<=100;i++) {
        f[i]=[];
        for (var j=0;j<=11;j++) f[i][j] = 0;
    }
    var len = {};
    var last = {};
    var first = {};
    
    for (var i=1;i<a.length;i++) {
        var y = 0;
        for (var j=0;j<a[i].length;j++) {
            y=y+x[a[i].charAt(j)];            
        }
        first[y] = z[a[i].charAt(0)];
        last[y] = z[a[i].charAt(a[i].length-1)];
        len[y] = a[i].length;
        // console.log(y);
    }
    var found = 1;
    while (found) {
        found = 0;
        for (var i=1;i<1024;i++) if (len[i]) {
            for (var j=i+1;j<1024;j++) if (len[j] && !len[i+j]) {
                for (var k in x) {
                    // console.log(i, j, x[k], i & (x[k]*2-1), j & (x[k]*2-1));
                    if (
                        ((i & (x[k]*2-1)) == i)
                        && 
                        ((j & (x[k]*2-1)) == 0)
                    ) {
                        len[i+j]=len[i]+len[j];
                        first[i+j] = first[i];
                        last[i+j] = last[j];
                        found = 1;
                        break;
                    }
                }
            }        
        }        
    }
    f[0][11] = 1;
    
    for (var i=1;i<1024;i++) if (len[i]) {
        h[len[i]][first[i]]++;
    }
    found = 1;
    var sum = 1;
    
    for (var i=1;i<=m;i++) {
        for (var j=0;j<=11;j++) {
            for (var k=1;k<1024;k++) {
                var p = len[k];
                var c1 = first[k];
                var c2 = last[k];                
                if (i-p >= 0 && c1<=j) {                    
                    // for (var c=0;c<=j;c++) {           
                        if (f[i-p][j]*h[p][c1] > 0) {
                            // console.log(i, last[k], i-p, j, p, c2, k, f[i][last[k]], f[i-p][j], h[p][c1]);
                            f[i][c2] = (f[i][c2]+f[i-p][j])%t;
                        }
                    // }
                }
            }
        }
        for (var j=0;j<=11;j++) {
            sum = (sum+f[i][j])%t;
        }
    }
    // console.log(f);
    /* 
    console.log(h);
    var sum = 1;
    for (var i=1;i<=m;i++) {
        for (var j=1;j<=i;j++) {
            f[i] += f[i-j]*h[j];
            f[i] = f[i]%t;
        }
        sum = (sum+f[i])%t;
    }
    */
    console.log(sum);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Hyper Strings Python Solution

#!/bin/python3

import os
import sys

#
# Complete the hyperStrings function below.
#
def hyperStrings(m, H):
    modul = 10 ** 9 + 7
    letters = "abcdefghij"
    H = [hyperstr for hyperstr in H if len(hyperstr) > 0]
    
    H_graded = {letter: [hyper_str for hyper_str in H if hyper_str[-1] == letter] for letter in letters}
    letter_graded = {letter : set() for letter in letters}
    for letter in letters:
        for hyper_end in H_graded[letter]:
            letter_graded[letter].add(hyper_end)
            for mid in letters:
                if mid == hyper_end[0]:
                    break
                to_add = [hyper_beg + hyper_end for hyper_beg in letter_graded[mid]]  
                if to_add:
                    letter_graded[letter].update(to_add)
    
    dp = [{letter: 0 for letter in letters} for length in range(m+1)]
    dp[0] = {letter: 1 for letter in letters}
    for length in range(1, m+1):
        for letter, graded in letter_graded.items():
            for supstr in graded:
                if length < len(supstr):
                    continue
                dp[length][letter] = (dp[length][letter] + dp[length - len(supstr)][supstr[0]]) % modul
        for index in range(len(letters) - 1, 0, -1):
            dp[length][letters[index - 1]] = (dp[length][letters[index - 1]] + dp[length][letters[index]]) % modul
    return sum([dp[length]['a'] for length in range(m + 1)]) % modul

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    nm = input().split()
    n = int(nm[0])
    m = int(nm[1])
    H = []
    while len(H) < n:
        H_item = input().split()
        H = H + H_item

    result = hyperStrings(m, H)
    fptr.write(str(result) + '\n')
    fptr.close()