Binar Axtarış Ağacının Yaradılması

İkitərəfli Axtarış Ağacı (İAA) kökü olan ikitərəfli ağacdır və aşağıdakı xüsusiyyətlərə malikdir:

• Sol alt ağac yalnız kökdən kiçik olan zirvələri ehtiva edir.

• Sağ alt ağac yalnız kökdən böyük olan zirvələri ehtiva edir.

• Bütün zirvələrin dəyərləri fərqlidir.

• Sol və sağ alt ağaclar rekursiv olaraq ikitərəfli axtarış ağacıdır.

Yeni zirvə əlavə edildikdə, aşağıdakı alqoritm tətbiq olunur:

1. Əgər ağac boşdursa, yeni zirvə kök olur və əlavə etmə prosesi başa çatır. Əks halda, 2-ci addıma keçin.

2. Cari zirvə olaraq ağacın kökünü elan edin.

3. Əgər yeni zirvənin dəyəri kökdən kiçikdirsə, onda:

   • Əgər kökün sol alt ağacı boşdursa, yeni zirvəni kökün sol oğlu olaraq təyin edin və dayanın.

   • Əks halda, cari zirvə olaraq sol alt ağacın kökünü təyin edin və 3-cü addımı təkrarlayın.

4. Əgər yeni zirvənin dəyəri kökdən böyükdürsə, onda:

   • Əgər kökün sağ alt ağacı boşdursa, yeni zirvəni kökün sağ oğlu olaraq təyin edin və dayanın.

   • Əks halda, cari zirvə olaraq sağ alt ağacın kökünü təyin edin və 3-cü addımı təkrarlayın.

İAA-nın strukturu giriş ardıcıllığından asılıdır. Müxtəlif ardıcıllıqlar, eyni rəqəmlərə malik olsalar da, müxtəlif strukturlar yarada bilər.

1 2 3 ardıcıllığını nəzərdən keçirək. Aşağıdakı İAA əldə edəcəyik:

Əgər giriş ardıcıllığı 2 1 3 şəklindədirsə, onda ağac belə olacaq:

Digər tərəfdən, müxtəlif giriş məlumatları eyni İAA strukturlarını yarada bilər. Məsələn, 2 1 3 ardıcıllığı, 4 6 2 ardıcıllığı ilə eyni İAA strukturunu yaradır. Ağac belə görünəcək:

Verilmiş n zirvələri olan İAA üçün, eyni İAA strukturunu yaradan neçə fərqli giriş ardıcıllığının olduğunu müəyyənləşdirin. Ağacın zirvələri 1..m diapazonundan dəyərlər alır.

Giriş verilənləri

Birinci sətir testlərin sayını t (t ≤ 100) ehtiva edir. Hər bir test iki tam ədəd n və m (1 ≤ n ≤ m ≤ 1000) ilə başlayır - İAA-dakı zirvələrin sayı və diapazonun maksimum dəyəri müvafiq olaraq. Növbəti sətir n tam ədəd a_i (1 ≤ a_{i }≤ 1000) ehtiva edir - İAA-nın qurulduğu ardıcıllıq.

Çıxış verilənləri

Hər bir test üçün, 1..m diapazonundan dəyərlər götürülərək eyni İAA strukturunu yaradan fərqli ardıcıllıqların sayını çıxarın. Nəticəni 1000003 modulu ilə çıxarın.

Qeyd: İkinci test üçün izah.

Eyni İAA strukturunu yaradan 8 giriş ardıcıllığı var (məlumatlar 1..4 aralığından götürülüb):

1. 2 1 3

2. 2 3 1

3. 2 1 4

4. 2 4 1

5. 3 1 4

6. 3 4 1

7. 3 2 4

8. 3 4 2

Nümunələr