Fişierul intrare/ieşire:	pitmutare.in, pitmutare.out	Sursă	Lot 2017 Baraj 3
Autor	Pit-Rada Vasile	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	1 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

Date de ieşire

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

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

Exemplu

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

Cum se trimit solutii?