Cerința

Se dau două permutări de ordin N.
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 și precizări

• 1 ≤ N ≤ 100.000
• Deoarece valorile cerute pot fi numere foarte mari se cere calcularea acestor valori modulo 1.000.000.007
• Î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[].

Exemplul 1:

abperm.in

1 3
1 2 3
3 2 1

abperm.out

8

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.

Exemplul 2:

abperm.in

2 3
1 2 3
3 2 1

abperm.out

4

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.