Mălina a scris pe trei foi de hârtie numere naturale.
Pe prima foaie a scris în ordine n numere naturale: a1 ,a2, . . . , an.
Pe a doua foaie a scris în ordine m numerele naturale: b1 ,b2, . . . , bm.
Pe a treia foaie a scris în ordine numerele: a 1 + b 1; a 1 + b 2; . . . ; a 1 + b m;
a 2 + b 1; a 2 + b 2; . . . ; a 2 + b m; . . . ;
a n + b 1, a n + b 2; . . . ; a n + b m .
De exemplu:
- dacă pe prima foaie scrie 5 2 4 şi pe a doua 1 1 atunci pe a treia foaie scrie 6 6 3 3 5 5.
- dacă pe prima foaie scrie 2 şi pe a doua 4 4 1 1 3 3 atunci pe a treia foaie scrie tot 6 6 3 3 5 5.
Din păcate Mălina a pierdut primele două foi şi nu îşi mai aminteşte nici câte numere a scris pe acestea şi nici care erau acele numere. Pentru că problema o depăşeste vă roagă pe voi să descoperiţi în câte moduri ar fi putut completa primele două foi ştiind numerele de pe a treia foaie.
Cerinţă
Scrieţi un program care primeşte ca date de intrare numerele de pe a treia foaie şi afişează în câte moduri ar fi putut completa Mălina primele două foi.
Date de intrare
Fişierul de intrare trifoi.in conţine pe prima linie un număr natural k, reprezentând numarul de numere scrise pe a treia foaie iar pe a doua linie va conţine k numere naturale separate prin câte un spaţiu reprezentând numerele de pe a treia foaie exact în ordinea în care au fost scrise de catre Malina.
Date de ieşire
Fişierul de ieşire trifoi.out va conţine o singura linie pe care va fi scris un singur număr natural reprezentând numărul de moduri în care pot fi completate primele două foi.
Restricţii şi precizari
1 ≤ k ≤ 10000
Numerele scrise pe cele trei foi precum si soluţia sunt numere naturale de cel mult 9 cifre.