Fişierul intrare/ieşire:	abperm.in, abperm.out	Sursă	ad-hoc
Autor		Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

ABPerm

Se dau două permutări de ordin N.

Cerinţă

Se precizează tipul T al cerinţei, care poate fi 1 sau 2:
1) Dacă T=1, atunci se cere să se afle câte permutări de ordin N se pot obţine după N paşi de "intercalare" a celor două permutări
2) Dacă T=2, atunci se cere să se afle câte permutări distincte de ordin N se pot obţine după N paşi de "intercalare" a celor două permutări

Date de intrare

Fişierul de intrare abperm.in conţine pe primul rând numerele T şi N. Pe al doilea rând, separate prin câte un spaţiu, se află elementele permutării a[], iar pe al treilea rând, separate prin spaţiu, se află elementele permutării b[].

Date de ieşire

În fişierul de ieşire abperm.out pe primul rând se află un singur număr natural reprezentând numărul cerut conform tipului cerinţei.

Restricţii

• 1 ≤ N ≤ 10^5
• Deoarece valorile cerute pot fi numere foarte mari se cere calcularea acestor valori modulo 10^9+7
• În general, prin „intercalare” a două şiruri a[] şi b[], de lungimi n şi respectiv m, se înţelege determinarea unui nou şir c[], de lungime n+m, care conţine toate elementele celor două şiruri a[] şi b[]. Elementele şirurilor a[] şi b[] formează subşiruri în c[]. Dacă pentru primele k elemente din c[] au fost folosite primele i elemente din a[] şi primele j elemente din b[], atunci pentru elementul al k+1-lea din c[] va fi folosit a[i+1] sau b[j+1]. La fiecare pas de intercalare se adaugă încă un element sirului care se construieşte c[].

Exemplu

Explicaţie

După 3 paşi de intercalare se pot obţine permutările: 1 2 3, 1 2 3, 1 3 2, 1 3 2, 3 1 2, 3 1 2, 3 2 1, 3 2 1

Explicaţie

După 3 paşi de intercalare se pot obţine 4 permutări distincte: 1 2 3, 1 3 2, 3 1 2, 3 2 1

Cum se trimit solutii?