#include <iostream>
#include <memory.h>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#include <map>
using namespace std;
typedef vector<string> v_s;
typedef pair<string,int> p_s_i;
typedef map<p_s_i,int> m_s_i;
v_s dict;
m_s_i memo;

//Trie Implementation
//Complexity:	O(Length of String) look up/insertion time
//Author:	Rajiv Mathews
//NOTE		Use g++ -O2 for faster map
class trie {
private:
	map<char, trie *> next;
	bool is_word;
public:
	//Add given word (string) to the trie
	void add_word(string s)
	{
		trie *curr_node = this;
		for(int i = 0 ; s[i] != '\0' ; ++i) {
			if(curr_node->next[s[i]] == NULL) curr_node->next[s[i]] = new trie();
			curr_node = curr_node->next[s[i]];
		}
		curr_node->is_word = true;
	}
	//Check if given word (string) is present in the trie
	bool is_present(string s)
	{
		trie *curr_node = this;
		for(int i = 0 ; s[i] != 0 ; ++i) {
			if(curr_node->next[s[i]] == NULL) return false;
			curr_node = curr_node->next[s[i]];
		}
		return curr_node->is_word;
	}
};
trie dict_words;


//Count ways to split substring of 's'  in to 'm'
//parts such that each part is atleast of length 'min_len'
int count_ways(string s, int m, int min_len)
{
	if(m==0) {
		return s.length()==0?1:0;
	}
	{
		p_s_i t;
		if(memo.find(t=make_pair(s,m)) != memo.end()) return memo[t];
	}
	int ways=0;
	for(int len=min_len ; len <= s.length() ; ++len) {
		if(dict_words.is_present(s.substr(0,len))) {
			ways += count_ways(s.substr(len,s.length()), m-1, min_len);
		}
	}
	memo[make_pair(s,m)] = ways;
	return ways;
}

int main(int argc, char *argv[])
{
	int m=atoi(argv[1]);
	string temp_input;
	int ans = 0;
	while(cin >> temp_input) {
		dict.push_back(temp_input);
		dict_words.add_word(temp_input);
	}
	for(v_s::iterator it=dict.begin() ; it!=dict.end() ; ++it) {
		ans += count_ways(*it, m, 3);
	}
	printf("%d\n", ans);
	return 0;
}