시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 52 32 30 65.217%

문제

UNIST는 Ulsan National Institute of Science and Technology의 약자이다. 어느 날 원이는 약자가 UNIST가 되는 다른 단어가 있는지에 대해 궁금해졌다.

단어 a의 길이를 len(a)로 표기하자. N개의 단어 W1, W2, ..., WN이 주어질 때, 단어 Wi (1 ≤ i ≤ N)로부터 앞에서 0글자 이상 len(Wi)글자 이하 택해서 만든 문자열을 Pi라 하자. 다시 말해, Pi는 Wi의 길이 len(Pi)인 접두사이다.

Pi (1 ≤ i ≤ N)들을 적당히 잘 정하여, P1+P2+...+PN이 UNIST가 되도록 하는 경우의 수를 구해보자. 단, 연산 +는 문자열 연결(string concatenation) 연산이다.

입력

첫 줄에 단어의 수 N이 주어진다.

이후 N개의 줄에 한 줄에 하나씩 N개의 단어 W1, W2, ..., WN가 주어진다.

Wi (1 ≤ i ≤ N)는 1개 이상의 영문 대문자로만 이루어진 문자열이다.

출력

P1+P2+...+PN이 UNIST가 되도록 P1, P2, ..., PN을 결정하는 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

제한

  • 1 ≤ N ≤ 100,000
  • len(Wi) ≤ 25

예제 입력 1

7
ULSAN
NATIONAL
INSTITUTE
OF
SCIENCE
AND
TECHNOLOGY

예제 출력 1

1

예제 입력 2

5
UNICODE
IS
THE
SPORTS
TIME

예제 출력 2

4

"UNI"+""+""+"S"+"T", "UN"+"IS"+"T"+""+"", "UN"+"IS"+""+""+"T", "UN"+"I"+""+"S"+"T"

예제 입력 3

2
UNIS
UT

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjE3ODQxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVU5JU1RcdWIyOTQgXHViYjM0XHVjNWM3XHVjNzU4IFx1YzU3ZFx1Yzc5MFx1Yzc3Y1x1YWU0Yz8iLCJkZXNjcmlwdGlvbiI6IjxwPlVOSVNUXHViMjk0IFVsc2FuIE5hdGlvbmFsIEluc3RpdHV0ZSBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5XHVjNzU4IFx1YzU3ZFx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjNTdkXHVjNzkwXHVhYzAwIFVOSVNUXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWIyZTRcdWI5NzggXHViMmU4XHVjNWI0XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjQgYVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgbGVuKGEpXHViODVjIFx1ZDQ1Y1x1YWUzMFx1ZDU1OFx1Yzc5MC4gTlx1YWMxY1x1Yzc1OCBcdWIyZThcdWM1YjQgVzxzdWI+MTxcL3N1Yj4sIFc8c3ViPjI8XC9zdWI+LCAuLi4sIFc8c3ViPk48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YjJlOFx1YzViNCBXPHNwYW4gc3R5bGU9XCJmb250LXNpemU6IDEwLjgzMzNweDtcIj5pPFwvc3Bhbj4mbmJzcDsoMSAmbGU7IGkgJmxlOyBOKVx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM1NWVcdWM1ZDBcdWMxMWMgMFx1YWUwMFx1Yzc5MCBcdWM3NzRcdWMwYzEgbGVuKFc8c3ViPmk8XC9zdWI+KVx1YWUwMFx1Yzc5MCBcdWM3NzRcdWQ1NTgmbmJzcDtcdWQwZGRcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBQPHN1Yj5pPFwvc3ViPlx1Yjc3YyBcdWQ1NThcdWM3OTAuIFx1YjJlNFx1YzJkYyBcdWI5ZDBcdWQ1NzQsIFA8c3ViPmk8XC9zdWI+XHViMjk0IFc8c3ViPmk8XC9zdWI+XHVjNzU4IFx1YWUzOFx1Yzc3NCBsZW4oUDxzdWI+aTxcL3N1Yj4pXHVjNzc4IFx1YzgxMVx1YjQ1MFx1YzBhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+UDxzdWI+aTxcL3N1Yj4mbmJzcDsoMSAmbGU7IGkgJmxlOyBOKVx1YjRlNFx1Yzc0NCBcdWM4MDFcdWIyZjlcdWQ3ODggXHVjNzk4IFx1YzgxNVx1ZDU1OFx1YzVlYywgUDxzdWI+MTxcL3N1Yj4rUDxzdWI+MjxcL3N1Yj4rLi4uK1A8c3ViPk48XC9zdWI+XHVjNzc0IFVOSVNUXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuIFx1YjJlOCwgXHVjNWYwXHVjMGIwICtcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzVmMFx1YWNiMChzdHJpbmcgY29uY2F0ZW5hdGlvbikgXHVjNWYwXHVjMGIwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgTlx1YWMxY1x1Yzc1OCBcdWIyZThcdWM1YjQgVzxzdWI+MTxcL3N1Yj4sIFc8c3ViPjI8XC9zdWI+LCAuLi4sIFc8c3ViPk48XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+VzxzdWI+aTxcL3N1Yj4mbmJzcDsoMSAmbGU7IGkgJmxlOyBOKVx1YjI5NCAxXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM2MDFcdWJiMzggXHViMzAwXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UDxzdWI+MTxcL3N1Yj4rUDxzdWI+MjxcL3N1Yj4rLi4uK1A8c3ViPk48XC9zdWI+XHVjNzc0IFVOSVNUXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4sIC4uLiwgUDxzdWI+TjxcL3N1Yj5cdWM3NDQgXHVhY2IwXHVjODE1XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPmxlbihXPHN1Yj5pPFwvc3ViPikgJmxlOyAyNTxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPjxjb2RlPiZxdW90O1VOSSZxdW90OysmcXVvdDsmcXVvdDsrJnF1b3Q7JnF1b3Q7KyZxdW90O1MmcXVvdDsrJnF1b3Q7VCZxdW90OywgJnF1b3Q7VU4mcXVvdDsrJnF1b3Q7SVMmcXVvdDsrJnF1b3Q7VCZxdW90OysmcXVvdDsmcXVvdDsrJnF1b3Q7JnF1b3Q7LCAmcXVvdDtVTiZxdW90OysmcXVvdDtJUyZxdW90OysmcXVvdDsmcXVvdDsrJnF1b3Q7JnF1b3Q7KyZxdW90O1QmcXVvdDssICZxdW90O1VOJnF1b3Q7KyZxdW90O0kmcXVvdDsrJnF1b3Q7JnF1b3Q7KyZxdW90O1MmcXVvdDsrJnF1b3Q7VCZxdW90OzxcL2NvZGU+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTc4NDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaGF0IGRvZXMgVU5JU1Qgc3RhbmQgZm9yPyIsImRlc2NyaXB0aW9uIjoiPHA+VU5JU1Qgc3RhbmRzIGZvciBVbHNhbiBOYXRpb25hbCBJbnN0aXR1dGUgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neS4gT25lIGRheSwgV29uIHdvbmRlcmVkIGlmIHRoZXJlIGlzIGFub3RoZXIgd29yZCB3aXRoIGFiYnJldmlhdGlvbiBVTklTVC48XC9wPlxyXG5cclxuPHA+Rm9yIGEgd29yZCB3LCBkZW5vdGUgaXRzIGxlbmd0aCBhcyBsZW4odykuIFN1cHBvc2UgdGhhdCBOIHdvcmRzIFc8c3ViPjE8XC9zdWI+LCBXPHN1Yj4yPFwvc3ViPiwgLi4uLCBXPHN1Yj5OPFwvc3ViPiBhcmUgZ2l2ZW4uIEZvciBlYWNoIDEmbmJzcDsmbGU7IGkmbmJzcDsmbGU7IE4sIGxldCBQPHN1Yj5pPFwvc3ViPiBiZSBzb21lIHByZWZpeCBvZiBXPHN1Yj5pPFwvc3ViPi4gTm90ZSB0aGF0IGxlbihQPHN1Yj5pPFwvc3ViPikgc2hvdWxkIHNhdGlzZnkgMCZuYnNwOyZsZTsgbGVuKFA8c3ViPmk8XC9zdWI+KSZuYnNwOyZsZTsgbGVuKFc8c3ViPmk8XC9zdWI+KS48XC9wPlxyXG5cclxuPHA+V29uIHdhbnRzIHRvIGNob29zZSZuYnNwO1A8c3ViPmk8XC9zdWI+ICgxJm5ic3A7JmxlOyBpJm5ic3A7JmxlOyBOKSBzYXRpc2Z5aW5nJm5ic3A7UDxzdWI+MTxcL3N1Yj4rUDxzdWI+MjxcL3N1Yj4rLi4uK1A8c3ViPk48XC9zdWI+Jm5ic3A7aXMgJnF1b3Q7VU5JU1QmcXVvdDsuIENvbXB1dGUmbmJzcDt0aGUgbnVtYmVyIG9mIHdheSBjaG9vc2luZyBQPHN1Yj5pPFwvc3ViPiAoMSZuYnNwOyZsZTsgaSZuYnNwOyZsZTsgTikgc3VjaCB0aGF0IFA8c3ViPjE8XC9zdWI+K1A8c3ViPjI8XC9zdWI+Ky4uLitQPHN1Yj5OPFwvc3ViPiBpcyAmcXVvdDtVTklTVCZxdW90Oy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lLCB0aGUgbnVtYmVyIG9mIHdvcmRzJm5ic3A7TiBpcyBnaXZlbi48XC9wPlxyXG5cclxuPHA+SW4gdGhlJm5ic3A7aSsxLXRoICgxJm5ic3A7JmxlOyBpJm5ic3A7JmxlOyBOKSBsaW5lIG9mIGlucHV0LCBXPHN1Yj5pPFwvc3ViPiBpcyBnaXZlbi48XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IFc8c3ViPmk8XC9zdWI+IGlzIG5vbi1lbXB0eSBzdHJpbmcgY29uc2lzdGVkIG9mIGNhcGl0YWwgbGV0dGVycyBvZiBFbmdsaXNoIGFscGhhYmV0LCBmb3IgZWFjaCAxJm5ic3A7JmxlOyBpJm5ic3A7JmxlOyBOLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSZuYnNwO2Fuc3dlciBvZiB0aGUgcHJvYmxlbSBtb2QgMSwwMDAsMDAwLDAwNy48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZSBhbnN3ZXIgb2YgdGhlIHByb2JsZW0gaXMgdGhlIG51bWJlciBvZiB3YXkgY2hvb3NpbmcgUDxzdWI+MTxcL3N1Yj4sIFA8c3ViPjI8XC9zdWI+LCAuLi4sIFA8c3ViPk48XC9zdWI+IHN1Y2ggdGhhdCBQPHN1Yj4xPFwvc3ViPitQPHN1Yj4yPFwvc3ViPisuLi4rUDxzdWI+TjxcL3N1Yj4gaXMgJnF1b3Q7VU5JU1QmcXVvdDsuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0IiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEmbmJzcDsmbGU7IE4mbmJzcDsmbGU7IDEwMCwwMDA8XC9saT5cclxuXHQ8bGk+bGVuKFc8c3ViPmk8XC9zdWI+KSZuYnNwOyZsZTsgMjU8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD48Y29kZT4mcXVvdDtVTkkmcXVvdDsrJnF1b3Q7JnF1b3Q7KyZxdW90OyZxdW90OysmcXVvdDtTJnF1b3Q7KyZxdW90O1QmcXVvdDssICZxdW90O1VOJnF1b3Q7KyZxdW90O0lTJnF1b3Q7KyZxdW90O1QmcXVvdDsrJnF1b3Q7JnF1b3Q7KyZxdW90OyZxdW90OywgJnF1b3Q7VU4mcXVvdDsrJnF1b3Q7SVMmcXVvdDsrJnF1b3Q7JnF1b3Q7KyZxdW90OyZxdW90OysmcXVvdDtUJnF1b3Q7LCAmcXVvdDtVTiZxdW90OysmcXVvdDtJJnF1b3Q7KyZxdW90OyZxdW90OysmcXVvdDtTJnF1b3Q7KyZxdW90O1QmcXVvdDs8XC9jb2RlPjxcL3A+XHJcbiJ9XQ==