Mahir has a really old fax machine. He is using this fax machine to communicate with his friends and family. But one day this machine starts glitching. As a result all of the space characters in the messages are skipped by the machine. As an example, if a friend sends Mahir the message the cake is a lie, the fax machine will print it as thecakeisalie. After some time this starts causing him problems since he cannot know where words start or end for sure. The message dragonfly might mean dragonfly, dragon fly or drag on fly. After struggling with these messages Mahir decides to write a program that can calculate how many ways are there to split a message printed by this fax machine into words.

1 Input/Output

You will be given a message and a list of possible words that can appear in the message. You are asked to print out in how many ways that a given message can be interpreted.

1.1 Input Format

The first line of the input file contains the received message as a string.

Second line of the input file is an integer D, specifying the number of words in Mahirs dictionary. Each of the following D lines contain a string, a distinct word in the dictionary. The dictionary does not have to be in the alphabetical order. A word in the dictionary might not appear in the message.

1.2 Output Format

Your program should calculate and print out the number of possible splittings of this message into words, using the words the given dictionary. This number can be really big, so you should calculate it in modulo 10⁹ +7. One of the biggest prime numbers that can fit into a 32 bit integer.

Hint: Whenever you perform an arithmetic operation, use long long int data type and take the modulo afterwards. This will prevent arithmetic overflow and ensure you get the right answer.

1.3 Example Input 1

hellomahir 3 hello world mahir

1.4 Example Output 2

1

This message can only be interpreted as hello mahir.

1.5 Example Input 2

thisisoverusedcarsalesman 14 ale ales car cars is man over overused ruse sale sales salesman this used

1.6 Example Output 2

6

All possible ways to interpret this message:

this is overused car salesman this is overused cars ales man this is over used car sales man this is over used car salesman this is over used cars ales man

1.7 Example Input 3

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 32 a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaa aaaaaaaaaaaaa aaaaaaaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

1.8 Example Output 2

147483634

Since this message can be split on each possible location, the number of possible interpretations of this message is 2³¹ = 2,147,483,648. 2,147,483,648 modulo 1,000,000,009 is 147,483,634.