SURF

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define task "SURF"
using namespace std;
using ll = long long;
using ld = long double;

constexpr int N = 1e4 + 2;
constexpr int mod = 2019;
constexpr int Inf = 1e9 + 7;
int m, n, a[N], b[N];
int dp[N][2], f[N][2], ans(0);
int cur[N];
vector<int> pos[N];

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
        cin >> a[i];

    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
        pos[b[i]].emplace_back(i);
    }
}

inline void Add(int &x, int y)
{
    x += y;
    if (x >= mod)
        x -= mod;
    else if (x < 0)
        x += mod;
}

void calDP(int sign)
{
    dp[0][0] = dp[0][1] = 0;
    f[0][0] = f[0][1] = 1;
    b[0] = sign;

    for (int i = 1; i <= m; ++i)
    {
        int max0(-Inf), max1(-Inf), cnt0(0), cnt1(0);
        for (int j = 0; j <= n; ++j)
            if (b[j] > a[i])
            {
                if (max1 < dp[j][1])
                {
                    max1 = dp[j][1];
                    cnt1 = f[j][1];
                }
                else if (max1 == dp[j][1])
                    Add(cnt1, f[j][1]);
            }
            else if (b[j] < a[i])
            {
                if (max0 < dp[j][0])
                {
                    max0 = dp[j][0];
                    cnt0 = f[j][0];
                }
                else if (max0 == dp[j][0])
                    Add(cnt0, f[j][0]);
            }
            else
            {
                if (max1 + 1 >= dp[j][0])
                {
                    dp[j][0] = max1 + 1;
                    f[j][0] = cnt1;
                }
                if (max0 + 1 >= dp[j][1])
                {
                    dp[j][1] = max0 + 1;
                    f[j][1] = cnt0;
                }
            }
        for (int j = (int)pos[a[i]].size() - 1; j > 0; --j)
        {
            if (dp[pos[a[i]][j]][0] == dp[pos[a[i]][j - 1]][0])
                Add(f[pos[a[i]][j]][0], -f[pos[a[i]][j - 1]][0]);

            if (dp[pos[a[i]][j]][1] == dp[pos[a[i]][j - 1]][1])
                Add(f[pos[a[i]][j]][1], -f[pos[a[i]][j - 1]][1]);
        }
    }
}

void Solve()
{
    calDP(0);

    int maxn = *max_element(&dp[0][0], (&dp[0][0]) + N * 2);

    for (int i = 1; i <= n; ++i)
    {
        if (dp[i][0] == maxn)
            (ans += f[i][0]) %= mod;
        if (dp[i][1] == maxn)
            (ans += f[i][1]) %= mod;
        dp[i][0] = f[i][0] = dp[i][1] = f[i][1] = 0;
    }

    calDP(N);

    int maxn2 = *max_element(&dp[0][0], (&dp[0][0]) + N * 2);

    //cout << maxn << " " << maxn2 << "\n";

    if (maxn2 > maxn)
    {
        maxn = maxn2;
        ans = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        //cout << i << ": " << dp[i][0] << " " << dp[i][1] << " " << f[i][0] << " " << f[i][1] << "\n";
        if (dp[i][0] == maxn)
            (ans += f[i][0]) %= mod;
        if (dp[i][1] == maxn)
            (ans += f[i][1]) %= mod;
    }

    if (maxn < 3)
    {
        cout << 0;
        return;
    }

    cout << maxn << "\n"
         << ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}