(DP) 백준 16500 문자열 판별

def sol(idx):
    global result
    if idx == len(S): # idx와 S의 길이가 같으면 의미가 없음
        result = 1
        return
    if dp[idx]: # 이미 검사를 했을 경우 return
        return
    dp[idx] = 1 # 검사를 했으니 1로 만들어준다.
    for i in range(len(A)): # 단어의 수만큼 반복
        if len(S[idx:]) >= len(A[i]): # 문자열의 길이가 단어보다 길다면 실행
            for j in range(len(A[i])): # 단어의 길이 만큼
                if A[i][j] != S[idx+j]: # 글자를 비교해서 다를 경우 break
                    break
		    else: # for문과 같은 레벨에 else를 둬서 break없이 빠져나온 경우를 처리하는 방법
                sol(idx+len(A[i])) # 단어만큼 끝났을 경우 (그 단어로만 이루어진 경우) return
    return
    
S = input()
A = []
dp = [0] * 101 # 메모리얼 리스트
for _ in range(int(input())):
    A.append(input())
result = 0
sol(0)
print(result)