Ogrodnik
VII OIG  Zawody dru»ynowe, etap I, runda II.
Dost¦pna pami¦¢: 64MB.
14 XII 2012
Bajtazar rozpocz¡a prac¦ jako ogrodnik. Pierwszym je-
go zleceniem jest ozdobienie kwiatem ka»dego z N do-
mów znajduj¡cych si¦ przy ulicy Poziomkowej. Wszyst-
kie dziaaki zlokalizowane s¡ po jednej stronie drogi. Pra-
cownik jest niespeanionym artyst¡ oraz nie lubi mono-
tonii, dlatego postanowia, »e s¡siednie ogrody nie bed¡
miaay kwiatów tego samego koloru. Bajtazar dysponu-
je K kolorami ro±lin. Na ile sposobów mo»e wykona¢
powierzone mu zadanie?
Wej±cie
W pierwszym wierszu standardowego wej±cia zapisano dwie liczby caakowite N , K (1 6 N 6 10 18 ,
2 6 K 6 10 9 ) , oznaczaj¡ce kolejno liczb¦ domów przy ulicy oraz liczb¦ rodzajów kwiatów, którymi dys-
ponuje Bajtazar. Mo»esz zaao»y¢, »e pracownik ma wystarczaj¡c¡ liczb¦ ro±lin ka»dego koloru.
Wyj±cie
W pierwszym wierszu standardowego wyj±cia powinna znale1¢ si¦ liczba sposobów, na jakie mo»e zosta¢ ozdo-
biona ulica. Wynik nale»y poda¢ modulo 10 9 + 9 (tzn. nale»y poda¢ reszt¦ z dzielenia wyniku przez 10 9 + 9 ).
Przykaady
Wej±cie:
3 3
Wyj±cie:
12
Wej±cie:
4 2
Wyj±cie:
2
Wej±cie:
2 5
Wyj±cie:
20