시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 120 24 17 36.170%

문제

상근이는 긴 단어를 작은 단어로 나누려고 한다. 이때, 작은 단어는 모두 입력으로 주어지는 집합 S에 포함되는 단어이어야 한다.

단어를 나누는 방법의 수를 구하는 프로그램을 작성하시오.

경우의 수가 매우 커질 수 있기 때문에 1337377로 나눈 나머지를 출력한다.

입력

첫째 줄에 긴 단어가 주어진다. 이 단어는 최대 300,000글자로 이루어져 있다.

둘째 줄에는 집합 S에 포함되어 있는 집합의 개수 N이 주어진다. (1 ≤ N ≤ 4,000)

다음 N개 줄에는 집합에 포함되어 있는 단어가 한 줄에 하나씩 주어진다. 단어는 최대 100글자로 이루어져 있고, 알파벳 소문자로만 이루어져 있다. 두 단어가 서로 같은 경우는 없다.

출력

첫째 줄에 문제의 설명에 나와있는 것 처럼 긴 단어를 작은 단어로 나누는 경우의 수를 출력한다.

예제 입력 1

abcd
4
a
b
cd
ab

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjMxNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyMDRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFlMzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWIyZThcdWM1YjRcdWI4NWMgXHViMDk4XHViMjA0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3OTFcdWM3NDAgXHViMmU4XHVjNWI0XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzlkMVx1ZDU2OSBTXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjRcdWI5N2MgXHViMDk4XHViMjA0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCAxMzM3Mzc3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFlMzQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjJlOFx1YzViNFx1YjI5NCBcdWNkNWNcdWIzMDAgMzAwLDAwMFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1ZDU2OSBTXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjOWQxXHVkNTY5XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZThcdWM1YjRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjMTFjXHViODVjIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHVhYzgzIFx1Y2M5OFx1YjdmYyBcdWFlMzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWIyZThcdWM1YjRcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InNldmVyaW5hIiwiZGVzY3JpcHRpb24iOiI8cD5BIHdvcmQgbmVlZHMgdG8gYmUgZGl2aWRlZCBpbnRvIHNtYWxsZXIgcGllY2VzIGluIHN1Y2ggYSB3YXkgdGhhdCBlYWNoIHBpZWNlIGlzIGZyb20gc29tZSBnaXZlbiBzZXQgb2Ygd29yZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZmluZCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRvIGRpdmlkZSB0aGUgZ2l2ZW4gd29yZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2luY2UgdGhhdCBudW1iZXIgY2FuIGJlIHJlYWxseSBiaWcsIHlvdSBoYXZlIHRvIG91dHB1dCB0aGUgcmVtYWluZGVyIG9mIGl0IGRpdmlkZWQgYnkgMTMzNzM3Ny4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBnaXZlbiB3b3JkIHdpdGggYSBtYXhpbXVtIGxlbmd0aCBvZiAzMDAgMDAwIGNoYXJhY3RlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgNCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyBvbmUgd29yZCBmcm9tIHRoZSBzZXQuIEVhY2ggd29yZCB3aWxsIGJlIGF0IG1vc3QgMTAwIGNoYXJhY3RlcnMgbG9uZy4gVGhlcmUgd2lsbCBiZSBubyB0d28gaWRlbnRpY2FsIHdvcmRzIGFuZCBhbGwgdGhlIGNoYXJhY3RlcnMgd2lsbCBiZSBsb3dlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uIG1vZHVsbyAxMzM3Mzc3LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d