Pitmutare

pitmutare

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

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.

Poveste şi cerinţă...

h2. Date de intrare

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.

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

h2. Date de ieşire

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

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

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 |

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

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

|
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") ==