Problem 2446: Antrenament

Cerință

Gigi este antrenor de fotbal și astăzi vrea să organizeze diferit antrenamentul. Până acum toți jucătorii se antrenau împreună, dar astăzi vrea să îi împartă pe grupe. Gigi are la echipă $N$ fotbaliști, fiecare având un rating ce reprezintă cât de talentat este: $a_1$ , $a_2$ , $a_3$ , $\dots$ , $a_N$ . Gigi vrea să organizeze antrenamentul astfel: vrea să îi împartă în $M$ grupe, reprezentate de $M$ subsecvențe consecutive în șirul $a$ . Fiecare grupă are asociat un rating. Șirul ratingurilor grupelor este strict crescător. Ratingul unei grupe este definit de cel mai slab rating al jucătorilor din grupa respectivă.

Exemplu

Dacă jucătorii au ratingurile $12, 10, 20, 20, 25, 30$ și grupele au ratingurile $10, 20, 30$ , putem face următoarele două partiții:

$12, 10$ | $20, 20, 25$ | $30$ ;
$12, 10, 20$ | $20, 25$ | $30$ .

Cunoscând numărul de fotbaliști, numărul de grupe, ratingurile fotbaliștilor și ratingurile asociate grupelor, se cere să îl ajutați pe Gigi să calculeze câte astfel de repartizări poate să creeze. Deoarece există foarte multe variante, afișați răspunsul modulo $1e9 + 7$ .

Date de intrare

Pe prima linie a fișierului de intrare antrenament.in se găsesc numerele $N$ (numărul de fotbaliști) si $M$ (numărul de grupe).
A doua linie conține $N$ numere: $a_1$ , $a_2$ , $a_3$ , $\dots$ , $a_N$ . (ratingurile fotbaliștilor).
A treia linie conține $M$ numere sortate crescător: $b_1$ , $b_2$ , $b_3$ , $\dots$ , $b_M$ (ratingurile grupelor).

Date de ieșire

Pe prima linie a fișierului de ieșire antrenament.out se va găsi un singur număr ce reprezintă numărul de modalități de a împărți fotbaliștii în grupe.

Restricții și precizări

Pentru $20\%$ din teste $N, M \leq 10$ ;
$N, M \leq 200 \ 000$ ;
Ratingurile jucătorilor $\leq 1 \ 000 \ 000 \ 000$ ;
Ratingurile echipelor $\leq 1 \ 000 \ 000 \ 000$ ;
Șirul ratingurilor grupelor este ordonat crescător;
Fiecare jucător aparține unei singure grupe.

Exemplul 1

antrenament.in

6 3
12 10 20 20 25 30
10 20 30

antrenament.out

Exemplul 2