#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &t) {
  t = 0;
  char ch = getchar();
  int f = 1;
  while ('0' > ch || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  do {
    (t *= 10) += ch - '0';
    ch = getchar();
  } while ('0' <= ch && ch <= '9');
  t *= f;
}
const int mod = (1e9);
int n, m;
int a[2010], b[2010];
long long dp[2010][2010];
long long s[2010][2010], ans;
int main() {
  read(n);
  read(m);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int j = 1; j <= m; j++) read(b[j]);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        dp[i][j] = s[i - 1][j - 1] + 1;
        dp[i][j] = (dp[i][j] % mod + mod) % mod;
        ans = (ans + dp[i][j]) % mod;
      }
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + dp[i][j];
      s[i][j] = (s[i][j] % mod + mod) % mod;
    }
  }
  printf("%lld\n", (ans + 1) % mod);
  return 0;
}
