HILO (Platina)

Besi x + 0.5 ədədini bilir, burada x 0 ilə n arasında olan bir tam ədəddir, daxil olmaqla.

Elza bu ədədi tapmağa çalışır. O, i böyükdür ya kiçikdir?" tipli suallar verə bilər, burada i 1-dən n-ə qədər olan bir ədəddir, daxil olmaqla. Besi "HI!" cavabını verir əgər i x + 0.5-dən böyükdürsə, və "LO!" əgər i x + 0.5-dən kiçikdirsə.

Elza aşağıdakı strategiyaya uyğun işləyir. O, n ədədindən ibarət bir siyahı yaradıb, burada hər bir ədəd 1-dən n-ə qədər bir dəfə rast gəlinir (başqa sözlə, bu siyahı n ölçülü bir permutasiyadır). Sonra o, bu siyahı ilə gedərək ədədləri ardıcıl olaraq təxmin etmək üçün çağırır. Lakin o, bütün faydasız sorğuları keçir. Belə ki, əgər Elza i ədədini soruşmalıdırsa və əvvəlcə j < i ədədini soruşub, Besi "HI!" cavabını veribsə, Elza i-ni soruşmur və siyahıdakı növbəti ədədə keçir. Eyni şəkildə, əgər o, əvvəlcə j > i ədədini soruşub və Besi "LO!" cavabını veribsə, Elza bu i ədədini də keçir və siyahıdakı növbəti ədədə keçir. Bu strategiyadan istifadə edərək, Elza hər zaman x-i unikal şəkildə müəyyən edəcək, hansı permutasiyanı yaratmasından asılı olmayaraq.

Əgər biz Besinin bütün "HI" və ya "LO" cavablarını bir sıraya s birləşdirsək, Besinin "HILO" demə sayını s sıradakı uzunluğu 4 olan alt sıranın "HILO"-ya bərabər olduğu hallar sayıdır.

Besi bilir ki, Elza bu strategiyadan istifadə edir və hətta artıq x ədədini seçib, lakin Elzanın hansı permutasiyadan istifadə etdiyini bilmir. Sizin vəzifəniz - Elzanın istifadə edə biləcəyi bütün permutasiyalar üçün Besinin "HILO" demə saylarının cəmini hesablamaqdır - 10^9 + 7 modulu ilə.

Giriş Məlumatları

Bir sətirdə n (1 ≤ n ≤ 5000) və x verilir.

Çıxış Məlumatları

HILO alt sıranın ümumi sayını 10^9 + 7 modulu ilə.

Nümunə 1

Bu testdə Besinin sayı 2.5.

Məsələn, əgər Elzanın permutasiyası (4, 1, 3, 2) olarsa, Besi "HILOHILO" deyəcək, - iki dəfə "HILO". Əgər Elzanın permutasiyası (3, 1, 2, 4) olarsa, Besi "HILOLO" deyəcək, "HILO" - bir dəfə.

Nümunə 2

Modul 10^9 + 7 ilə cəmi çıxış etməyi unutmayın.