NLCS

#define task "NLCS"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e4 + 5;
constexpr int mod = 123456789;
int m, n;
int a[N], b[N], dp[N], f[N], lcs[N], LCS[N];
vector<int> s;
vector<int> pos[N * 2];

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

    for (int i = 1; i <= m; ++i)
    {
        cin >> a[i];
        s.emplace_back(a[i]);
    }

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

#define Find(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin() + 1)
void Compress()
{
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());

    for (int i = 1; i <= m; ++i)
        a[i] = Find(s, a[i]);
    for (int i = 1; i <= n; ++i)
        b[i] = Find(s, b[i]);
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
        pos[b[i]].emplace_back(i);

    dp[0] = 1;

    for (int i = 1; i <= m; ++i)
    {
        int ans(0), res(0);

        for (int j = 0; j <= n; ++j)
        {
            if (a[i] == b[j])
            {
                lcs[j] = ans;
                f[j] = res;
            }
            else
            {
                lcs[j] = LCS[j];
                f[j] = dp[j];
            }

            if (LCS[j] + 1 > ans)
            {
                ans = LCS[j] + 1;
                res = dp[j];
            }
            else if (LCS[j] + 1 == ans)
                (res += dp[j]) %= mod;
        }

        for (int j = (int)pos[a[i]].size() - 1; j > 0; --j)
            if (lcs[pos[a[i]][j]] == lcs[pos[a[i]][j - 1]])
                (f[pos[a[i]][j]] -= f[pos[a[i]][j - 1]]) %= mod;
        // cerr << "ok\n";

        swap(f, dp);
        swap(lcs, LCS);
    }

    int ans(0), res(0);

    for (int i = 0; i <= n; ++i)
        if (LCS[i] > ans)
        {
            ans = LCS[i];
            res = dp[i];
        }
        else if (LCS[i] == ans)
            (res += dp[i]) %= mod;

    cout << ans << " " << (res + mod) % mod;
}

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();
    Compress();
    Solve();
}