시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 78 13 9 32.143%

문제

상근이는 긴 단어를 작은 단어로 나누려고 한다. 이때, 작은 단어는 모두 입력으로 주어지는 집합 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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJzZXZlcmluYSIsImRlc2NyaXB0aW9uIjoiPHA+QSB3b3JkIG5lZWRzIHRvIGJlIGRpdmlkZWQgaW50byBzbWFsbGVyIHBpZWNlcyBpbiBzdWNoIGEgd2F5IHRoYXQgZWFjaCBwaWVjZSBpcyBmcm9tIHNvbWUgZ2l2ZW4gc2V0IG9mIHdvcmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0byBkaXZpZGUgdGhlIGdpdmVuIHdvcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNpbmNlIHRoYXQgbnVtYmVyIGNhbiBiZSByZWFsbHkgYmlnLCB5b3UgaGF2ZSB0byBvdXRwdXQgdGhlIHJlbWFpbmRlciBvZiBpdCBkaXZpZGVkIGJ5IDEzMzczNzcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgZ2l2ZW4gd29yZCB3aXRoIGEgbWF4aW11bSBsZW5ndGggb2YgMzAwIDAwMCBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDQgMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgb25lIHdvcmQgZnJvbSB0aGUgc2V0LiBFYWNoIHdvcmQgd2lsbCBiZSBhdCBtb3N0IDEwMCBjaGFyYWN0ZXJzIGxvbmcuIFRoZXJlIHdpbGwgYmUgbm8gdHdvIGlkZW50aWNhbCB3b3JkcyBhbmQgYWxsIHRoZSBjaGFyYWN0ZXJzIHdpbGwgYmUgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgZnJvbSB0aGUgdGFzayBkZXNjcmlwdGlvbiBtb2R1bG8gMTMzNzM3Ny48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=