pitmutare

Pitmutare

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

Poveste şi cerinţă...

Pitmutare este un joc de cărţi pentru două persoane, în care fiecare jucător are un pachet întreg de $N$ cărţi numerotate de la $1$ la $N$. Cei doi jucători îşi amestecă pachetul şi una câte una vor pune pe masă câte o carte. Jucătorul care are cartea mai mare câştigă un punct. În caz de egalitate nimeni nu primeşte punctul. Jocul se încheie când se epuizează cele două pachete.
 
Pentru anumite poziţii de la $1$ la $N$ se cunoaşte cartea primului jucător, iar pentru celelalte poziţii se cunoaşte cartea celui de al doilea jucător.
 
Cunoscând numărul $N$ de cărţi, o valoare $S$ şi cărţile cunoscute pentru cei doi jucători, se cere să se determine pentru câte configuraţii ale cărţilor necunoscute primul jucător va obţine exact $S$ puncte.

h2. Date de intrare

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

Fişierul $pitmutare.in$ conţine pe prima linie numerele $N$ şi $S$ separate printr-un spaţiu. Pe a doua linie sunt descrise în ordine cărţile primului jucător. Această linie conţine $N$ valori între $0$ şi $N$. Valorile de $0$ se găsesc pe poziţiile cărţilor necunoscute, celelalte numere reprezintă cărţile cunoscute. Pe a treia linie sunt descrise în acelaşi fel cărţile celui de al doilea jucător.

h2. Date de ieşire

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

Fişierul $pitmutare.out$ va conţine un singur număr reprezentând răspunsul la cerinţă *$modulo 10^9^+7$*.

h2. Restricţii

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

* $0 ≤ S < N ≤ 300$
* Pentru teste în valoare de $10$ de puncte $N ≤ 8$
* Pentru teste în valoare de $20$ de puncte $N ≤ 18$
* Pentru teste în valoare de $40$ de puncte $N ≤ 30$
* Pentru teste în valoare de $60$ de puncte $N ≤ 80$
* Pentru teste în valoare de $20$ de puncte valorile cunoscute pentru cei doi jucători sunt distincte

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

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

|4 2
4 2 0 0
0 0 4 2
|2

|
h3. Explicaţie

...

 
Configuraţiile în care primul jucător câştigă $2$ puncte sunt:
$4 2 1 3$
$1 3 4 2$
 
$4 2 3 1$
$3 1 4 2$
 

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