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.
Cerință
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 .
Restricții și precizări
0 ≤ S < N ≤ 300- Pentru teste în valoare de
10de puncteN ≤ 8 - Pentru teste în valoare de
20de puncteN ≤ 18 - Pentru teste în valoare de
40de puncteN ≤ 30 - Pentru teste în valoare de
60de puncteN ≤ 80 - Pentru teste în valoare de
20de puncte valorile cunoscute pentru cei doi jucători sunt distincte
Exemplu
pitmutare.in
4 2
4 2 0 0
0 0 4 2
pitmutare.out
2
Explicatii
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