Yatan inəklər
Fermer Conun müxtəlif ölçülərdə n inəyi var. Əvvəlcə o, hər bir inək üçün fərdi bir tövlə tikdi, lakin indi bəzi inəklər öz tövlələrini böyüdüblər. Xüsusilə, əvvəlcə FC n tövlə tikdi, ölçüləri t[1], t[2], ..., t[n], halbuki inəklər indi s[1], s[2], ..., s[n] ölçüsündədirlər (1 ≤ s[i], t[i] ≤ 10^9).
Hər gecə inəklər yatmaq üçün tövlə axtarma ritualını keçirirlər. İnək i yalnız o zaman tövlədə j yata bilər ki, o, tövləyə sığsın (s[i] ≤ t[j]). Hər bir tövlədə bir inək yerləşdirilə bilər.
İnəklərin tövlələrlə uyğunlaşdırılması maksimumdur deyəcəyik, əgər hər bir tövlə təyin olunmuş inək orada yerləşə bilirsə və tövləsi təyin olunmamış hər bir inək boş tövlələrdən heç birinə yerləşə bilmirsə.
Maksimum uyğunluqların sayını 10^9 + 7 modulu ilə hesablayın.
Giriş məlumatları
Birinci sətir n ədədini (1 ≤ n ≤ 3000) ehtiva edir. İkinci sətir n tam ədəd s[1], s[2], ..., s[n] ehtiva edir. Üçüncü sətir n tam ədəd t[1], t[2], ..., t[n] ehtiva edir.
Çıxış məlumatları
Maksimum uyğunluqların sayını 10^9 + 7 modulu ilə çıxarın.
Nümunə
Bütün doqquz maksimum uyğunluqların siyahısı. Cütlük (i, j) inək i-nin tövlə j-yə təyin olunduğunu göstərir.
(1, 1), (2, 2), (3, 4) (1, 1), (2, 3), (3, 4) (1, 1), (2, 4) (1, 2), (2, 3), (3, 4) (1, 2), (2, 4) (1, 3), (2, 2), (3, 4) (1, 3), (2, 4) (1, 4), (2, 2) (1, 4), (2, 3)