Gizli Santa

Hər Milad bayramında alqoritm həvəskarları icmasının üzvləri bir-birinə hədiyyələr göndərirlər. Bu ənənə bəzən problemlərə və münaqişələrə səbəb olur, çünki bəzi iştirakçılar digərlərindən daha çox hədiyyə alır. Bu il icma, Secret Santa adlanan koordinasiya olunmuş və ədalətli bir sistem tətbiq etməyə qərar verdi.

Secret Santa sisteminin ideyası çox sadədir: icmanın hər bir üzvünə hədiyyə göndərəcəyi bir şəxs təyin edilir. Beləliklə, hər iştirakçı bir hədiyyə hazırlayır və bir hədiyyə alır. Bəzi iştirakçılar özlərini təyin edə bilərlər, bu halda onlar özlərinə hədiyyə göndərirlər.

İcma bu ideyaya həvəslə yanaşır və indi kimin kimə hədiyyə göndərəcəyini müəyyən etmək istəyir. Bununla belə, poçt sisteminin necə işlədiyini nəzərə almaq lazımdır - bir şəhərdən digərinə bağlamanın çatdırılması həmin gün küləyin gücündən asılıdır.

n icma üzvü var. Hər iştirakçı ayrı bir şəhərdə yaşayır, şəhərlər 1-dən n-ə qədər nömrələnmişdir. Əgər küləyin sürəti a-ya bərabərdirsə, onda hədiyyə ilə bağlama k şəhərindən l şəhərinə yalnız o halda göndərilə bilər ki, k - n + a < l < k + a.

Sizin vəzifəniz - icma üzvlərini təyin etməyin yollarının sayını tapmaqdır ki, hamı eyni gündə hədiyyələrini göndərə bilsin, həmin gün küləyin sürətini nəzərə alaraq. Çünki bu rəqəm çox böyük ola bilər, sizə yalnız 10^9 + 7 modulu ilə dəyəri tapmaq lazımdır.

Giriş məlumatları

Birinci sətir testlərin sayı z-ni (1 ≤ z ≤ 10) ehtiva edir. Daha sonra testlərin təsvirləri gəlir.

Hər bir test ayrıca bir sətirdə yerləşdirilib və iki tam ədəd n və a (1 ≤ a ≤ 200, 1 ≤ n ≤ 10^6, a < n) ehtiva edir - müvafiq olaraq icma üzvlərinin sayı və küləyin gücü.

Çıxış məlumatları

Hər bir test üçün bir tam ədəd çıxarın: icma üzvlərinin bir-birinə təyin edilə biləcəyi yolların sayı, 10^9 + 7 modulu ilə hesablanmış.