== include(page="template/taskheader" task_id="abperm") ==

Se dau două permutări de ordin $N$.
 
h2. 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

Poveste şi cerinţă...

h2. 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[]$.

Fişierul de intrare $abperm.in$ ...

h2. 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.

În fişierul de ieşire $abperm.out$ ...

h2. 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[]$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. abperm.in |_. abperm.out |

| 1 3
  1 2 3
  3 2 1
| 6
|
 
h3. Explicaţie
 
După 3 paşi de intercalare se pot obţine permutările: 1 2 3, 1 2 3, 1 3 2, 3 1 2, 3 2 1, 3 2 1
 
table(example). |_. abperm.in |_. abperm.out |
| 2 3
  1 2 3
  3 2 1
| 4

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. 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

...

== include(page="template/taskfooter" task_id="abperm") ==

== include(page="template/taskfooter" task_id="abperm") ==