Cow and Treats

After a successful year of milk production, Farmer John is rewarding his cows with their favorite treat: tasty grass!

On the field, there is a row of $n$ units of grass, each with a sweetness $s_i$. Farmer John has $m$ cows, each with a favorite sweetness $f_i$ and a hunger value $h_i$. He would like to pick two disjoint subsets of cows to line up on the left and right side of the grass row. There is no restriction on how many cows must be on either side. The cows will be treated in the following manner:

  • The cows from the left and right side will take turns feeding in an order decided by Farmer John.
  • When a cow feeds, it walks towards the other end without changing direction and eats grass of its favorite sweetness until it eats $h_i$ units.
  • The moment a cow eats $h_i$ units, it will fall asleep there, preventing further cows from passing it from both directions.
  • If it encounters another sleeping cow or reaches the end of the grass row, it will get upset. Farmer John absolutely does not want any cows to get upset.

Note that grass does not grow back. Also, to prevent cows from getting upset, not every cow has to feed since FJ can choose a subset of them.

Surprisingly, FJ has determined that sleeping cows are the most satisfied. If FJ orders optimally, what is the maximum number of sleeping cows that can result, and how many ways can FJ choose the subset of cows on the left and right side to achieve that maximum number of sleeping cows (modulo $10^9+7$)? The order in which FJ sends the cows does not matter as long as no cows get upset.Input

The first line contains two integers $n$ and $m$ ($1 \le n \le 5000$, $1 \le m \le 5000$)  — the number of units of grass and the number of cows.

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le n$)  — the sweetness values of the grass.

The $i$-th of the following $m$ lines contains two integers $f_i$ and $h_i$ ($1 \le f_i, h_i \le n$)  — the favorite sweetness and hunger value of the $i$-th cow. No two cows have the same hunger and favorite sweetness simultaneously.Output

Output two integers  — the maximum number of sleeping cows that can result and the number of ways modulo $10^9+7$.Examplesinput

5 2
1 1 1 1 1
1 2
1 3

output

2 2

input

5 2
1 1 1 1 1
1 2
1 4

output

1 4

input

3 2
2 3 2
3 1
2 1

output

2 4

input

5 1
1 1 1 1 1
2 5

output

0 1

Note

In the first example, FJ can line up the cows as follows to achieve $2$ sleeping cows:

  • Cow $1$ is lined up on the left side and cow $2$ is lined up on the right side.
  • Cow $2$ is lined up on the left side and cow $1$ is lined up on the right side.

In the second example, FJ can line up the cows as follows to achieve $1$ sleeping cow:

  • Cow $1$ is lined up on the left side.
  • Cow $2$ is lined up on the left side.
  • Cow $1$ is lined up on the right side.
  • Cow $2$ is lined up on the right side.

In the third example, FJ can line up the cows as follows to achieve $2$ sleeping cows:

  • Cow $1$ and $2$ are lined up on the left side.
  • Cow $1$ and $2$ are lined up on the right side.
  • Cow $1$ is lined up on the left side and cow $2$ is lined up on the right side.
  • Cow $1$ is lined up on the right side and cow $2$ is lined up on the left side.

In the fourth example, FJ cannot end up with any sleeping cows, so there will be no cows lined up on either side.

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}

template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
}
return res;
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}

template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;

constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}

template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }

Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular& operator++() { return *this += 1; }
Modular& operator--() { return *this -= 1; }
Modular operator++(int) { Modular result(*this); *this += 1; return result; }
Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
Modular operator-() const { return Modular(-value); }

template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (mod())
);
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}

Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

template <typename U>
friend const Modular<U>& abs(const Modular<U>& v) { return v; }

template <typename U>
friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

template <typename U>
friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

template <typename U>
friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

private:
Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
assert(b >= 0);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
return to_string(number());
}

template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
return stream << number();
}

template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
typename common_type<typename Modular<T>::Type, int64_t>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = (int) 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> s(n);
for (int i = 0; i < n; i++) {
    cin >> s[i];
--s[i];
}
vector<int> f(m), h(m);
for (int i = 0; i < m; i++) {
    cin >> f[i] >> h[i];
--f[i];
}
vector<vector<int>> all(n);
for (int i = 0; i < n; i++) {
    all[s[i]].push_back(i);
  }
  vector<int> L(m, -1);
vector<int> R(m, -1);
for (int i = 0; i < m; i++) {
    if (h[i] > (int) all[f[i]].size()) {
continue;
}
L[i] = all[f[i]][h[i] - 1];
R[i] = all[f[i]][(int) all[f[i]].size() - h[i]];
}
int ans = 0;
Mint ways = 0;
vector<int> nl(n);
vector<int> nr(n);
vector<int> nb(n);
for (int cut = -1; cut < n; cut++) {
    for (int i = 0; i < n; i++) {
      nl[i] = nr[i] = nb[i] = 0;
    }
    for (int i = 0; i < m; i++) {
      if (L[i] == -1) {
        continue;
      }
      if (L[i] <= cut && R[i] > cut) {
nb[f[i]] += 1;
}
if (L[i] <= cut) {
        nl[f[i]] += 1;
      }
      if (R[i] > cut) {
nr[f[i]] += 1;
}
}
int cur_ans = 0;
Mint cur_ways = 1;
if (cut >= 0) {
bool ok = false;
for (int i = 0; i < m; i++) {
        if (L[i] == cut) {
          ok = true;
          break;
        }
      }
      if (!ok) {
        continue;
      }
      cur_ans += 1;
      int rs = 0;
      for (int i = 0; i < m; i++) {
        if (f[i] == s[cut] && L[i] != cut && R[i] > cut) {
++rs;
}
}
if (rs > 0) {
cur_ans += 1;
cur_ways *= rs;
}
}
for (int i = 0; i < n; i++) {
      if (cut >= 0 && i == s[cut]) {
continue;
}
int two = nl[i] * nr[i] - nb[i];
if (two > 0) {
cur_ans += 2;
cur_ways *= two;
continue;
}
int one = nl[i] + nr[i];
if (one > 0) {
cur_ans += 1;
cur_ways *= one;
}
}
if (cur_ans > ans) {
ans = cur_ans;
ways = 0;
}
if (cur_ans == ans) {
ways += cur_ways;
}
}
cout << ans << " " << ways << '\n';
  return 0;
}