시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 3 3 20.000%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

abcd
4
a
b
cd
ab

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjMxNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyMDRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFlMzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWIyZThcdWM1YjRcdWI4NWMgXHViMDk4XHViMjA0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNzkxXHVjNzQwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM5ZDFcdWQ1NjkgU1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4XHVjNWI0XHViOTdjIFx1YjA5OFx1YjIwNFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMTMzNzM3N1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZTM0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjZDVjXHViMzAwIDMwMCwwMDBcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWQ1NjkgU1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDQsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWMxMjRcdWJhODVcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1YWM4MyBcdWNjOThcdWI3ZmMgXHVhZTM0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM3OTFcdWM3NDAgXHViMmU4XHVjNWI0XHViODVjIFx1YjA5OFx1YjIwNFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoic2V2ZXJpbmEiLCJkZXNjcmlwdGlvbiI6IjxwPkEgd29yZCBuZWVkcyB0byBiZSBkaXZpZGVkIGludG8gc21hbGxlciBwaWVjZXMgaW4gc3VjaCBhIHdheSB0aGF0IGVhY2ggcGllY2UgaXMgZnJvbSBzb21lIGdpdmVuIHNldCBvZiB3b3Jkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gZGl2aWRlIHRoZSBnaXZlbiB3b3JkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGF0IG51bWJlciBjYW4gYmUgcmVhbGx5IGJpZywgeW91IGhhdmUgdG8gb3V0cHV0IHRoZSByZW1haW5kZXIgb2YgaXQgZGl2aWRlZCBieSAxMzM3Mzc3LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGdpdmVuIHdvcmQgd2l0aCBhIG1heGltdW0gbGVuZ3RoIG9mIDMwMCAwMDAgY2hhcmFjdGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyA0IDAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIG9uZSB3b3JkIGZyb20gdGhlIHNldC4gRWFjaCB3b3JkIHdpbGwgYmUgYXQgbW9zdCAxMDAgY2hhcmFjdGVycyBsb25nLiBUaGVyZSB3aWxsIGJlIG5vIHR3byBpZGVudGljYWwgd29yZHMgYW5kIGFsbCB0aGUgY2hhcmFjdGVycyB3aWxsIGJlIGxvd2VyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIGZyb20gdGhlIHRhc2sgZGVzY3JpcHRpb24gbW9kdWxvIDEzMzczNzcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d