Komanda qurulması

Hər il fermer Con öz $n$ inəyini əyalət yarmarkasında keçirilən "ən yaxşı inək" müsabiqəsinə gətirir. Onun qatı rəqibi fermer Pol da öz $m$ inəyini müsabiqəyə gətirir.

n + m inəyin hər birinə tam ədəd olan fərdi qiymət (bal) verilir. Lakin bu il müsabiqənin nəticəsi $k$ inəkdən ibarət komandalar vasitəsilə aşağıdakı qaydada müəyyən ediləcək: fermer Con və fermer Pol öz inəklərindən $k$ ədəddən ibarət komanda seçirlər. Sonra iki komandanın inəkləri öz qiymətlərinə uyğun olaraq cütlərə bölünür: FC komandasında ən yüksək qiymətə malik inək FP komandasında ən yüksək qiymətə malik inəklə qarşılaşır, ikinci ən yüksək qiymətə malik inəklər növbəti cütü təşkil edir və s. FC yalnız o halda qalib gəlir ki, hər bir cütdə onun inəyi FP komandasının müvafiq inəyindən ciddi şəkildə yüksək qiymətə malik olsun.

FC-yə köməklik edərək, onun və FP-nin öz komandalarını elə seçə biləcəyi fərqli üsulların sayını hesablayın ki, FC müsabiqəni qazansın. Başqa sözlə, FC tərəfindən seçilmiş $k$ inəkdən ibarət çoxluq ilə FP tərəfindən seçilmiş $k$ inəkdən ibarət çoxluqdan ibarət hər bir fərqli cütü, əgər bu cütdə FC qalib gəlirsə, saymaq lazımdır. Cavabı 10^9 + 9 modulu üzrə çıxarın.