Zadanie dokładnie wygląda tak:
Neon składa się z dwóch słów. Na ile sposobów można zgasić niektóre litery w neonie, tak by litery, które pozostaną zapalone, w obu słowach układały się w ten sam niepusty podciąg? Ile różnych podciągów da się w ten sposób uzyskać?
Wejście
W pierwszym wierszu standardowego wejścia zapisano dwie liczby całkowite n,m(0 <= n, m <= 2000), długość pierwszego oraz drugiego słowa. W drugim oraz trzecim wierszu wejścia znajdują się dwa słowa z neonu,składające się z małych liter alfabetu angielskiego.
Wyjście
W pierwszym wierszu standardowego wyjścia należy wypisać ile różnych wspólnych pod słów mają dwa ciągi na wejściu. Ponieważ wynik może być bardzo duży, należy obliczyć jego resztę z dzielenia modulo 10e9+ 9.
Przykłady:
Wejście:
5 9
alina
balladyna
Wyjście:
14
Wejście:
11 9
supermarket
stokrotka
Wyjście:
17
Przepraszam że od razu nie wkleiłem tutaj całej treści zadania