Artan altqruplar#6857
Bir sıra p(1), p(2), …, p(N) ədədlərindən 1, 2, … , N ibarət olan ardıcıllıq, əgər ardıcıllığın bütün elementləri fərqlidirsə, permutasiya adlanır.
Bir permutasiya p k elementdən ibarət artma alt ardıcıllığı ehtiva edir deyilir, əgər
1 ≤ i_1 < i_2 < … < i_k ≤ N
və
p(i_1) < p(i_2) < … < p(i_k)
şərtlərini ödəyirsə.
Bir permutasiya p B elementdən ibarət artma alt ardıcıllığı ehtiva edir və B+1 elementdən ibarət artma alt ardıcıllığı ehtiva etmir deyildikdə, bu permutasiyanın B ədədi artma dərəcəsi adlanır.
Sizdən tələb olunur ki, verilmiş N ədədinə görə artma dərəcəsi B olan permutasiyaların sayını hesablayan bir proqram yazasınız. Belə permutasiyaların sayı çox böyük ola biləcəyi üçün, onun 1000000000 ilə tam bölünməsindən qalanı hesablamaq lazımdır.
Giriş faylı bir sətirdən ibarətdir. Sətir iki tam ədəd N və B (1 ≤ N ≤ 40, 1 ≤ B ≤ 5) ehtiva edir, bir və ya daha çox boşluqla ayrılmışdır.
Çıxış faylı bir tam ədəd ehtiva edir ki, bu da artma dərəcəsi B olan permutasiyaların sayının 1000000000 ilə tam bölünməsindən qalandır.
Nümunə 1