Forming a String with Given Words

Given a string (s) and a list of words, determine whether (s) can be formed by concatenating words from the list. Each word may be used multiple times. Use dynamic programming to decide if every prefix of (s) can be constructed from the given words. For example, if (s = \texttt{applepie}) and the list of words is [apple, pie], then the answer is (\texttt{True}) because (s) can be split into (\texttt{apple}) and (\texttt{pie}).

inputFormat

The input is read from standard input (stdin) with the following format:\

1. The first line contains the string (s).\
2. The second line contains an integer (n) representing the number of words.\
3. The next (n) lines each contain one word.\ \ For example:\ applepie\ 2\ apple\ pie

outputFormat

Output a single line to standard output (stdout) containing either (True) or (False) indicating whether the string (s) can be formed by concatenating the provided words.## sample

applepie
2
apple
pie

True