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

Poveste şi cerinţă...

Un arbore binar este un arbore cu rădăcină în care fiecare nod are maxim 2 fii. Un arbore binar de căutare ({*B*}inary {*S*}earch {*T*}ree) este un arbore binar în care fiecare nod are asociată o valoare, iar valoarea unui nod este strict mai mare decât toate valorile din subarborele său stâng şi strict mai mică decât toate valorile din subarborele său drept. Un exemplu de arbore binar de căutare este cel din stânga iar unul greşit în dreapta (deoarece *9* se află în subarborele stâng al lui *5* şi *3*).
 
!{width: 300px; margin: 10px}problema/countbst?arbore1.png!
!{width: 300px; margin: 10px}problema/countbst?arbore2.png!
 
h2. Cerinţă
 
Cunoscând numerele naturale *N*, *K* şi un şir *A{~1~}*, *A{~2~}*, ...{*A{~K~}*} cu toate elementele numere naturale distincte nenule mai mici sau egale cu *N*, vi se cere să număraţi câţi arbori binari de căutare există cu *N* noduri având valorile asociate nodurilor *1*, *2*, ... *N* (în orice ordine validă), astfel încât şirul *A{~1~}*, *A{~2~}*, ...{*A{~K~}*} să formeze un lanţ în arbore *în această ordine*. De exemplu, pentru *N=8, K=5, A=(6, 7, 5, 3, 4)*, arborele de mai sus din stânga este unul valid.

h2. Date de intrare

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

Fişierul de intrare *$countbst.in$* va conţine pe prima linie un număr natural *T* (numărul de teste), urmat de *T* teste. Fiecare test va fi descris prin două linii:
● Pe prima linie se vor găsi două numere naturale *N* şi *K* separate printr-un spaţiu.
● Pe linia a doua se vor găsi cele *K* numere naturale nenule distincte *A{~1~}*, *A{~2~}*, ...{*A{~K~}*} separate şi urmate de un spaţiu

h2. Date de ieşire