kswap

Fie $A$ = $(a_1,a_2 , …, a_N)$ o permutare a mulțimii $\set{1, 2,…, N}$.

Permutarea $A$ o numim K-swap dacă prin aplicarea algoritmului de sortare bubble-sort sunt necesare exact $K$ swapuri (interschimbări) pentru ca aceasta să devină permutarea identică.

Reamintim algoritmul bubble-sort:

do {
   ok = 1;
   for (i = 1; i < N; i++)
       if (a[i] > a[i+1]) {
           swap(a[i], a[i+1]);
           ok = 0;
       }
}while( ok == 0 ); 

Cerinţă

Pentru $N$ și $K$ dat să se determine numărul de permutări K-swap ale mulțimii $\set{1, 2, …, N}$. Exemplu: pentru $N = 3$ și $K = 2$, dintre permutările $\set{1,2,3}$, $\set{1,3,2}$, $\set{2,1,3}$, $\set{2,3,1}$, $\set{3,1,2}$, $\set{3,2,1}$, permutările 2-swap sunt următoarele: $\set{2,3,1}$, $\set{3,1,2}$.

Date de intrare

Fişierul de intrare kswap.in conţine pe prima linie două numere naturale nenule $N$, $K$ separate prin câte un spaţiu, cu semnificația descrisă anterior.

Date de ieşire

Pe prima linie a fişierului kswap.out se va scrie un singur număr natural $M$ ce reprezintă numărul de permutări K-swap, modulo $30103$ ale mulțimii $\set{1, 2, …, N}$.

Restricţii şi precizări

• $ 1 \leq N \leq 150$
• $ 1 \leq K \leq N * (N-1) / 2$
• Prin permutarea identică înțelegem permutarea $\set{1, 2, …, N}$.

Exemplu

kswap.in

4 5 

kswap.out

3  

Explicaţii

Mulțimea $\set{1, 2, 3, 4}$ are $24$ de permutări:

Doar $3$ dintre acestea sunt permutări $5-swap$ : $\set{3,4,2,1}$,$\set{4,2,3,1}$,$\set{4,3,1,2}$.