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)