String Discrimination

Interview

Time limit2sMemory limit512 MB

Summary

Given a target string S and up to 100 words, decide whether S is a concatenation of words from the list, each reusable any number of times.

Level: Medium4 of 10
Topics: Dynamic programming, String, Hash map
Solved: No attempts yet

Problem

A string $S$ consisting of lowercase alphabet letters and a list of words $A$ are given. Write a program that determines whether $S$ can be formed by concatenating one or more strings from $A$ without any spaces. A word in $A$ may be used multiple times.

Input

The first line gives a string $S$ whose length is at most 100. The second line gives the number of strings in $A$ , $N$ ( $1 \le N \le 100$ ). The following $N$ lines give the words in $A$ , one per line. Each string in $A$ consists only of lowercase alphabet letters and its length does not exceed 100.

Output

Output 1 if $S$ can be formed from strings in $A$ , and 0 otherwise.

Examples1

Example 1
Input
```
softwarecontest
2
software
contest
```
Expected output
```
1
```