На Факултетот за информатички науки и компјутерско инженерство (ФИНКИ), по одредени предмети, се врши усогласување на наставната програма. Тоа се прави бидејќи, претходно, еден наставник предавал по една програма, друг наставник по друга програма, итн.

Во конкретниот проблем се усогласуваат две програми. Програмите се дадени како низа од големи букви од абецедата, каде што секоја буква означува активност од одреден тип.

Усогласувањето се прави на следниот начин:

    1. Нека двете програми се дадени како текстуални низи S1 и S2. На пример, програмата на едниот наставник може да е дадена како S1="AHSUA", додека на другиот како S2="KSUUHAS".

    2. Сега, треба да се најде текстуална низа T со најмала можна должина, на која што S1 и S2 ќе бидат нејзини поднизи. (Одредена низа S претставува подниза на T, доколку постои начин да се добие S од T преку бришење на одреден број (можеби 0) знаци од низата Т).

    3. На овој начин, T ќе ги содржи сите активности (букви) од низите S1 и S2 - во соодветен редослед, па и двајцата наставници ќе бидат задоволни со програмата која што ќе се користи по предметот.

На пример, нека оригиналните програми се S1="CBA" и S2="CAB". Во овој случај, постојат две програми со најмала можна должина - "CABA" и "CBAB". Забележете дека, на пример, "CAB" не е адекватно решение, бидејќи распоредот на активностите не е соодветен - S1="CBA" не претставува подниза на "CAB".

Слично, нека S1="UYZX" и С2="UXZYXZ". Во овој случај, постојат 4 можни програми со најмала можна должина (7): UXZYXZX, UXZYZXZ, UXYZYXZ, UYXZYXZ.

Напишете програма која, за дадени програми S1 и S2, ќе отпечати колку програми T постојат, кои се со бараната најмала можна должина.

Влез

Во првата линија е запишана програмата на едниот наставник (S1), додека во втората линија е запишана програмата на другиот наставник (S2). Програмите ќе содржат помеѓу 1 и 1000 знаци, и ќе се состојат само од големите латинични букви ('A'-'Z').

Забелешка: Во тест случаи кои носат најмалку 30% од поените, S1 и S2 ќе бидат составени од по најмногу 8 знаци, и ќе содржат само две букви ('A' и 'B').

Излез

Отпечатете го бараниот број на програми - по модул 750 083. (За дадени два цели броја А и B, A модул B го означува остатокот кој се добива при делење на A со B. На пример, бројот 7 станува 1 по модул 3.)

Ограничувања

Временско ограничување: 2 seconds
Мемориско ограничување: 64 megabytes

Примери

влез
CBA
CAB

излез
2

влез
UYZX
UXZYXZ

излез
4