0167. How Many Programs?

Input file name: programs.in
Output file name: programs.out
Time limit: 3 s
Memory limit: 64 megabytes

Little Jaina loves programming. She already knows N programming constructions! Now Jaina thinks how many programs of a given length L she can compose using these constructions. Help her to count them!

Note that Jaina ignores any spaces and blank lines in her program and counts only printable characters. Also Jaina considers different two programs if they are equal as strings, but different sequences of constructions were used to create them.

Of course Jaina does not require that the program must compile. She will learn about compilers on the next lesson.

Input file

The first line of the input file contains number of constructions 1 ≤ N ≤ 1000. The next N lines contain constructions themselves. Length of any of these lines does not exceed 255 characters. If a construction occures more than once, all occurences are considered different, so there are exactly N different constructions Jaina knows. The strings contain only characters with ASCII codes from 32 to 126. Jaina wants that all blanks in the strings must be ignored.

The last line of the input contains a single integer 1 ≤ L ≤ 1000.

Output file

Output the number of different programs Jaina can compose.

Examples:

programs.inprograms.out
3 begin clrscr end 1720


Source: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Author: Andrew Lopatin

Discuss       Submit a solution



Printable version