2. Triedenie ponožiek

Bobov tajný koníček je výroba umeleckých diel z rôznych kusov oblečenia. Momentálne sa snaží imitovať svetoznáme maľby. Už sa mu poradilo vyrobiť napodobeninu Gitaristu od Pabla Picassa len pomocou postrihaných nohavíc, podobizeň Mony Lízy od Leonarda da Vinciho pomocou šiltoviek a Van Goghove Slnečnice kombináciou rôznofarebných šálov. Na dalšie umelecké dielo sa rozhodol použiť ponožky.

Bob má v skrini najviac 26 rôznych farieb ponožiek, a tieto farby označíme malými písmenami anglickej abecedy. Ponožky sú v skrini naukladané pekne vedľa seba a hoci to na prvý pohľad môže vyzerať chaoticky, Bob v tom má systém. Aby si Bob svoj systém nepokazil, jediné čo môže pri výrobe umeleckého diela spraviť je vybrať jeden súvislý úsek ponožiek, niektoré z ponižiek použiť na umelecké dielo, zvyšné ponožky popárovať a popárované odložiť do šuflíka. Žiadne ponožky nesmie vrátiť do skrine, žiadne mu nakoniec nemôžu ostať nepoužité a párovať spolu môže samozrejme len ponožky rovnakých farieb.

Bob vie, koľko ponožiek, akých farieb bude potrebovať na svoje umelecké dielo a tiež vie, ako sú naukladané jeho ponožky v skrini. Veľmi by ho zaujímalo, koľkými spôsobmi môže vybrať zo skrine súvislý úsek ponožiek tak, aby mu po odobratí niekoľkých párov ponožiek ostali práve tie ponožky, čo potrebuje na umelecké dielo. Na poradí ponožiek vo vybranom úseku nezáleží.

Úloha

Máme dané dva reťazce písmen \(P\) a \(Q\). Nájdite počet rozdelení \(P\) na \(P_1\), \(P_2\) a \(P_3\), pre ktoré platí:

• \(P_1\) + \(P_2\) + \(P_3\) = \(P\).
• Každé písmeno abecedy má v \(P_2\) aspoň toľko výskytov ako v \(Q\).
• Počet výskytov každého písmena v \(P_2\) má rovnakú paritu ako v počet jeho výskytov v \(Q\).

Formát vstupu

Vstup má dva riadky, na prvom z nich je reťazec \(P\) a na druhom reťazec \(Q\). Oba reťazce sa skladajú z malých písmen anglickej abecedy, ich dĺžka je aspoň 1 a najviac milión. (Samozrejme riešenie, ktoré zvláda len kratšie reťazce dostane čiastkové body.)

Napriek tomu, že časový limit je pomerne voľný, v poslednej sade môžu mať aj riešenia s optimálnou časovou problémy. Ak teda chcete plný počet bodov, odporúčame vyhnúť sa pomalším programovacím jazykom. Časový limit pre všetky vstupy je 1 sekunda, pamäťový limit je 512 megabajtov a horné obmedzenia na dĺžky reťazcov v jednotlivých sadách sú postupne \(100\), \(2\,000\), \(20\,000\), \(100\,000\) a \(1\,000\,000\).

Formát výstupu

Na výstup vypíšte jedno číslo, počet vyhovujúcich úsekov ponožiek v \(P\).

Príklady

Input:

xxxxyy
xx

Output:

6

Input:

abababa
a

Output:

8

Input:

nanananananananabatman
banan

Output:

7

V prvom vstupe, máme tri možnosti ako vybrať xx, jednu možnosť ako vybrať xxxx, xxyy alebo xxxxyy. V druhom sú to štyrikrát a, dvakrát bab a dvakrát ababa. V treťom vstupe sú štyri možnosti, kedy úsek končí b a tri možnosti kedy končí ba.