#include <bits/stdc++.h>
using namespace std;
using edge = struct {
  long long to;
  long long cost;
};
struct point {
  long long x;
  long long y;
  bool operator<(const point& p) const {
    if (x == p.x) return y < p.y;
    return x < p.x;
  }
};
struct undirected_edge {
  long long from;
  long long to;
  long long cost;
  bool operator<(const undirected_edge& ue) const { return cost < ue.cost; }
};
const long long N_DIGITS = 60;
const long long MOD = 1e9 + 7;
const long long INF = MOD * MOD;
const long double EPS = 1e-9;
const long double PI = 3.14159265358979323846;
std::vector<point> dirs = {{-1, 0}, {1, 0},   {0, 1},  {0, -1}, {1, 1},
                           {-1, 1}, {-1, -1}, {1, -1}, {0, 0}};
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...);
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
struct MaxFlow {
  struct F_edge {
    long long to, rev, capacity;
    F_edge(long long to, long long rev, long long capacity)
        : to(to), rev(rev), capacity(capacity) {}
  };
  vector<vector<F_edge>> graph;
  long long n_vertex;
  std::vector<long long> level, iter;
  MaxFlow(long long n_vertex) : n_vertex(n_vertex) { graph.resize(n_vertex); }
  void add_edge(long long from, long long to, long long capacity) {
    graph[from].push_back({to, long long(graph[to].size()), capacity});
    graph[to].push_back({from, long long(graph[from].size()) - 1, 0});
  }
  void bfs(long long source) {
    level = std::vector<long long>(n_vertex, -1);
    level[source] = 0;
    queue<long long> q;
    q.push(source);
    while (!q.empty()) {
      long long vertex = q.front();
      q.pop();
      for (long long(i) = 0; (i) < (graph[vertex].size()); (i)++) {
        long long target = graph[vertex][i].to;
        long long cap_target = graph[vertex][i].capacity;
        if (cap_target > 0 && level[target] < 0) {
          level[target] = level[vertex] + 1;
          q.push(target);
        }
      }
    }
  }
  long long dfs(long long vertex, long long sink, long long flow) {
    if (vertex == sink) return flow;
    for (long long& i = iter[vertex]; i < graph[vertex].size(); i++) {
      long long target = graph[vertex][i].to;
      long long cap_target = graph[vertex][i].capacity;
      long long rev_target = graph[vertex][i].rev;
      if (cap_target > 0 && level[vertex] < level[target]) {
        long long d = dfs(target, sink, min(cap_target, flow));
        if (d > 0) {
          graph[vertex][i].capacity -= d;
          graph[target][rev_target].capacity += d;
          return d;
        }
      }
    }
    return 0;
  }
  long long dinic(long long source, long long sink) {
    long long flow = 0;
    while (true) {
      bfs(source);
      if (level[sink] < 0) return flow;
      iter = std::vector<long long>(n_vertex, 0);
      long long f;
      while ((f = dfs(source, sink, INF)) > 0) flow += f;
    }
  }
};
class UnionFind {
  std::vector<long long> parents, set_size;
  long long n_groups;

 public:
  UnionFind() {}
  UnionFind(long long n) {
    parents = set_size = std::vector<long long>(n);
    n_groups = n;
    for (long long(i) = 0; (i) < (n); (i)++) {
      parents[i] = i;
      set_size[i] = 1LL;
    }
  }
  long long root_find(long long x) {
    if (parents[x] == x) return x;
    return parents[x] = root_find(parents[x]);
  }
  void unite(long long x, long long y) {
    x = root_find(x);
    y = root_find(y);
    if (x == y) return;
    parents[y] = x, set_size[x] += set_size[y];
    n_groups--;
  }
  bool is_same(long long x, long long y) {
    return root_find(x) == root_find(y);
  }
  long long size(long long x) { return set_size[root_find(x)]; }
  long long union_count() const { return n_groups; }
};
struct Doubling {
  long long n;
  long long sz;
  std::vector<std::vector<long long>> next;
  Doubling(std::vector<long long>& edge) : n(edge.size()), sz(62) {
    next.resize(sz, std::vector<long long>(n, -1));
    for (long long(i) = 0; (i) < (n); (i)++) next[0][i] = edge[i];
    for (long long(k) = 0; (k) < (sz - 1); (k)++)
      for (long long(i) = 0; (i) < (n); (i)++)
        next[k + 1][i] = next[k][next[k][i]];
  }
  long long get(long long i, long long x) {
    long long ret = i;
    for (long long(bit) = 0; (bit) < (sz); (bit)++) {
      if (!(x >> bit & 1)) continue;
      ret = next[bit][ret];
    }
    return ret;
  }
  long long lower_bound(long long i, long long j) {
    long long cur = i, acc = 0;
    for (long long(wid) = sz - 1; (wid) >= 0; (wid)--) {
      if (next[wid][cur] < j) {
        acc += 1LL << wid;
        cur = next[wid][cur];
      }
    }
    return min(n, acc + 1);
  }
};
class LowestCommonAncestor {
 public:
  long long N, logN;
  std::vector<long long> depth, len;
  std::vector<vector<edge>> tree;
  std::vector<std::vector<long long>> parents;
  LowestCommonAncestor(long long n, long long offset = -1,
                       bool is_weighted = true) {
    N = n;
    logN = 0;
    while (N > (1LL << logN)) logN++;
    depth = std::vector<long long>(N);
    len = std::vector<long long>(N);
    parents =
        std::vector<std::vector<long long>>(logN, std::vector<long long>(N));
    tree = std::vector<vector<edge>>(N);
    input(N, offset, is_weighted);
    init(0, -1, 0, 0);
    build();
  }
  void add_edge(long long from, long long to, long long dist) {
    tree[from].push_back({to, dist});
    tree[to].push_back({from, dist});
  }
  void input(long long n, long long offset = -1, bool is_weighted = true) {
    for (long long(i) = 0; (i) < (n - 1); (i)++) {
      long long a, b, d = 1;
      cin >> (a) >> (b);
      a += offset, b += offset;
      if (is_weighted) cin >> (d);
      add_edge(a, b, d);
    }
  }
  void init(long long source, long long parent, long long d, long long l) {
    depth[source] = d;
    parents[0][source] = parent;
    len[source] = l;
    for (long long(i) = 0; (i) < (tree[source].size()); (i)++) {
      long long target = tree[source][i].to;
      long long cost = tree[source][i].cost;
      if (target == parent) continue;
      init(target, source, d + 1, cost + l);
    }
  }
  void build() {
    for (long long(k) = 0; (k) < (logN - 1); (k)++)
      for (long long(n) = 0; (n) < (N); (n)++) {
        if (parents[k][n] < 0)
          parents[k + 1][n] = -1;
        else
          parents[k + 1][n] = parents[k][parents[k][n]];
      }
  }
  long long query(long long u, long long v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (long long(k) = 0; (k) < (logN); (k)++)
      if ((depth[v] - depth[u]) >> k & 1) v = parents[k][v];
    if (u == v) return u;
    for (long long(k) = logN - 1; (k) >= 0; (k)--) {
      if (parents[k][u] != parents[k][v]) {
        u = parents[k][u];
        v = parents[k][v];
      }
    }
    return parents[0][u];
  }
  long long distance(long long u, long long v) {
    long long w = query(u, v);
    return len[u] + len[v] - 2 * len[w];
  }
};
struct BinaryIndexedTree {
  long long n, ini;
  std::vector<long long> dat;
  BinaryIndexedTree(long long n, long long ini = 0)
      : dat(n + 1, ini), n(n), ini(ini){};
  long long update_func(long long val, long long d) { return val + d; }
  long long query(long long i) {
    if (i < 0) return ini;
    long long ret = 0;
    for (long long j = i; j >= 0; j = (j & (j + 1)) - 1) {
      ret = update_func(ret, dat[j]);
    }
    return ret;
  }
  long long query(long long l, long long r) { return query(r) - query(l - 1); }
  long long lower_bound(long long key) {
    if (key <= 0) return 0;
    long long left = 0, right = 1;
    while (right <= n) right *= 2;
    for (long long i = right; i > 0; i /= 2) {
      if (left + i <= n && dat[left + i - 1] < key) {
        key -= dat[left + i - 1];
        left += i;
      }
    }
    return left;
  }
  void update(long long i, long long val) {
    if (i < 0) return;
    for (long long j = i; j < n; j |= j + 1) {
      dat[j] = update_func(val, dat[j]);
    }
  }
};
struct SegmentTree {
  long long n, ini, minimize;
  std::vector<long long> dat;
  SegmentTree(long long n_, bool minimize_ = true) {
    n = 1;
    minimize = minimize_;
    if (minimize)
      ini = INF;
    else
      ini = -INF;
    while (n < n_) n *= 2;
    dat.resize(2 * n - 1);
    for (long long(i) = 0; (i) < (2 * n - 1); (i)++) dat[i] = ini;
  };
  void update(long long idx, long long val) {
    idx += n - 1;
    if (minimize && dat[idx] <= val) return;
    if (!minimize && dat[idx] >= val) return;
    dat[idx] = val;
    while (idx > 0) {
      idx = (idx - 1) / 2;
      if (minimize)
        dat[idx] = min(dat[idx * 2 + 1], dat[idx * 2 + 2]);
      else
        dat[idx] = max(dat[idx * 2 + 1], dat[idx * 2 + 2]);
    }
  }
  long long query(long long l, long long r) {
    r++;
    return query_segment(l, r, 0, 0, n);
  }
  long long query_segment(long long a, long long b, long long idx, long long l,
                          long long r) {
    assert(a < b);
    if (r <= a || b <= l) return ini;
    if (a <= l && r <= b)
      return dat[idx];
    else {
      long long seg1 = query_segment(a, b, idx * 2 + 1, l, (l + r) / 2);
      long long seg2 = query_segment(a, b, idx * 2 + 2, (l + r) / 2, r);
      if (minimize)
        return min(seg1, seg2);
      else
        return max(seg1, seg2);
    }
  }
};
template <class Target>
class RerootingTreeDP {
 public:
  using T = typename Target::type;
  struct DP_edge {
    long long to, rev;
    T value;
  };

 private:
  long long n;
  void dfs_fwd(long long source, long long parent) {
    long long par_idx = -1;
    vector<T> values;
    for (long long(i) = 0; (i) < (tree[source].size()); (i)++) {
      const DP_edge& e = tree[source][i];
      if (e.to == parent) {
        par_idx = i;
        continue;
      }
      dfs_fwd(e.to, source);
      values.push_back(e.value);
    }
    if (par_idx != -1) {
      long long src_idx = tree[source][par_idx].rev;
      tree[parent][src_idx].value = Target::merge(values);
    }
  }
  void dfs_bwd(long long source, long long parent) {
    vector<T> values;
    for (auto&& e : tree[source]) values.push_back(e.value);
    values = Target::evaluate(values);
    for (long long(i) = 0; (i) < (tree[source].size()); (i)++) {
      const DP_edge& e = tree[source][i];
      if (e.to == parent) continue;
      tree[e.to][e.rev].value = values[i];
      dfs_bwd(e.to, source);
    }
  }

 public:
  UnionFind uf;
  vector<vector<DP_edge>> tree;
  RerootingTreeDP(long long n) : n(n), uf(n), tree(n) {}
  void add_edge(long long u, long long v, T val) {
    assert(!uf.is_same(u, v));
    tree[u].push_back({v, long long(tree[v].size()), val});
    tree[v].push_back({u, long long(tree[u].size()) - 1, val});
    uf.unite(u, v);
  }
  void dp() {
    std::vector<bool> visited(n, false);
    for (long long(i) = 0; (i) < (n); (i)++) {
      if (visited[uf.root_find(i)]) continue;
      dfs_fwd(i, -1);
      visited[uf.root_find(i)] = true;
    }
    visited.assign(n, false);
    for (long long(i) = 0; (i) < (n); (i)++) {
      if (visited[uf.root_find(i)]) continue;
      dfs_bwd(i, -1);
      visited[uf.root_find(i)] = true;
    }
  }
  long long size() const { return tree.size(); }
};
struct Merger {
  using type = long long;
  static type merge(const vector<type>& value) {
    long long ret = 1;
    for (auto&& v : value) ret += v;
    return ret;
  }
  static vector<type> evaluate(const vector<type>& value) {
    const long long n_children = value.size();
    std::vector<long long> L(n_children + 1, 0), R(n_children + 1, 0);
    for (long long(i) = 0; (i) < (n_children); (i)++)
      L[i + 1] = L[i] + value[i];
    for (long long(i) = n_children - 1; (i) >= 0; (i)--)
      R[i] = R[i + 1] + value[i];
    std::vector<long long> ret(n_children);
    for (long long(i) = 0; (i) < (n_children); (i)++)
      ret[i] = L[i] + R[i + 1] + 1;
    return ret;
  }
};
struct StronglyConnectedComponents {
  long long n;
  std::vector<std::vector<long long>> graph, graph_rev, dag, cmp;
  std::vector<long long> order, visited, cmp_idx;
  StronglyConnectedComponents() {}
  StronglyConnectedComponents(long long sz)
      : n(sz), graph(sz), graph_rev(sz), visited(sz), cmp_idx(sz) {}
  void add_edge(long long from, long long to) {
    graph[from].push_back(to);
    graph_rev[to].push_back(from);
  }
  void input(long long m, long long offset = -1) {
    long long a, b;
    for (long long(i) = 0; (i) < (m); (i)++) {
      cin >> (a) >> (b);
      add_edge(a + offset, b + offset);
    }
  }
  long long operator[](long long k) { return cmp_idx[k]; }
  void dfs_fwd(long long source) {
    visited[source] = 1;
    for (long long(i) = 0; (i) < (graph[source].size()); (i)++) {
      long long target = graph[source][i];
      if (!visited[target]) dfs_fwd(target);
    }
    order.push_back(source);
  }
  void dfs_bwd(long long source, long long num) {
    visited[source] = 1, cmp_idx[source] = num;
    cmp[num].push_back(source);
    for (long long(i) = 0; (i) < (graph_rev[source].size()); (i)++) {
      long long target = graph_rev[source][i];
      if (!visited[target]) dfs_bwd(target, num);
    }
  }
  long long build() {
    fill((visited).begin(), (visited).end(), 0);
    order.clear();
    for (long long(i) = 0; (i) < (n); (i)++)
      if (!visited[i]) dfs_fwd(i);
    fill((visited).begin(), (visited).end(), 0);
    long long num = 0;
    for (long long(i) = order.size() - 1; (i) >= 0; (i)--) {
      if (!visited[order[i]]) {
        dag.push_back(std::vector<long long>());
        cmp.push_back(std::vector<long long>());
        dfs_bwd(order[i], num++);
      }
    }
    for (long long(i) = 0; (i) < (n); (i)++)
      for (long long to : graph[i])
        if (cmp_idx[i] != cmp_idx[to]) dag[cmp_idx[i]].push_back(cmp_idx[to]);
    for (long long(i) = 0; (i) < (num); (i)++) {
      sort((dag[i]).begin(), (dag[i]).end());
      dag[i].erase(unique((dag[i]).begin(), (dag[i]).end()), dag[i].end());
    }
    return num;
  }
};
struct CombinationMemo {
  long long sz, mod;
  std::vector<long long> facts, facts_inv, minv;
  CombinationMemo(long long sz, long long _mod) : sz(sz), mod(_mod) {
    facts.resize(sz + 5);
    facts_inv.resize(sz + 5);
    minv.resize(sz + 5);
    init();
  }
  void init() {
    facts[0] = facts[1] = 1;
    minv[1] = 1;
    facts_inv[0] = facts_inv[1] = 1;
    for (long long(i) = (2); (i) < (sz + 3); (i)++) {
      facts[i] = (i * facts[i - 1]) % mod;
      minv[i] = mod - minv[mod % i] * (mod / i) % mod;
      facts_inv[i] = facts_inv[i - 1] * minv[i] % mod;
    }
  }
  long long nCk(long long n, long long r) {
    if (n == r && n == 0)
      return 1;
    else if (n <= 0 || r < 0 || r > n)
      return 0;
    long long val = (facts[n] * facts_inv[n - r]) % mod;
    val *= facts_inv[r];
    return val % mod;
  }
};
struct Grid2D {
  std::vector<vector<edge>> graph;
  long long Width, Height;
  Grid2D(long long w, long long h) : Width(w), Height(h) {
    graph.resize(w * h);
  }
  long long pos_to_idx(point p) { return p.y * Width + p.x; }
  point idx_to_pos(long long idx) { return {idx % Width, idx / Width}; }
  bool undefined_region(point p, std::vector<std::vector<bool>>& block) {
    if (p.x < 0 || p.x > Width - 1) return true;
    if (p.y < 0 || p.y > Height - 1) return true;
    if (block[p.x][p.y]) return true;
    return false;
  }
  void build(std::vector<std::vector<bool>>& block, long long val = 1) {
    for (long long(x) = 0; (x) < (Width); (x)++)
      for (long long(y) = 0; (y) < (Height); (y)++) {
        point p = {x, y};
        long long idx1 = pos_to_idx(p);
        long long idx2;
        if (block[x][y]) continue;
        for (long long(i) = 0; (i) < (4); (i)++) {
          point d = dirs[i], nxt = {x + d.x, y + d.y};
          idx2 = pos_to_idx(nxt);
          if (!undefined_region(nxt, block)) graph[idx1].push_back({idx2, val});
        }
      }
  }
};
long long gcd(long long m, long long n) {
  long long a = max(m, n);
  long long b = min(m, n);
  while (b != 1 && b != 0) {
    a %= b;
    swap(a, b);
  }
  return b == 1 ? 1 : a;
}
long long lcm(long long m, long long n) { return m / gcd(m, n) * n; }
long long power_mod(long long a, long long power, long long mod) {
  long long value = 1;
  while (power != 0) {
    if (power & 1) value = (value * a) % mod;
    a = (a * a) % mod;
    power = power >> 1;
  }
  return value % mod;
}
long long modinv(long long a, long long mod) {
  return power_mod(a, mod - 2, mod);
}
long long power_normal(long long a, long long power) {
  long long value = 1;
  while (power != 0) {
    if (power & 1) value = value * a;
    a = a * a;
    power = power >> 1;
  }
  return value;
}
std::vector<std::vector<long long>> pascal_triangle(long long n) {
  std::vector<std::vector<long long>> comb(n, std::vector<long long>(n));
  comb[0][0] = 1;
  for (long long(i) = (1); (i) < (n + 1); (i)++)
    for (long long(j) = 0; (j) < (i + 1); (j)++) {
      comb[i][j] += comb[i - 1][j];
      if (j > 0) comb[i][j] += comb[i - 1][j - 1];
    }
  return comb;
}
long long combination(long long n, long long r, long long mod) {
  if (n == r && n == 0)
    return 1;
  else if (n <= 0 || r < 0 || r > n)
    return 0;
  long long numerator = 1;
  long long denomenator = 1;
  for (long long i = 0; i < r; i++) {
    long long num = (n - i) % mod, den = (i + 1) % mod;
    (numerator *= num) %= mod;
    (denomenator *= modinv(den, mod)) %= mod;
  }
  return (numerator * denomenator) % mod;
}
long double log_combination(long long n, long long r) {
  if (n == r && n == 0)
    return 0;
  else if (n <= 0 || r < 0 || r > n)
    return -INF;
  long double val = 0;
  for (long long i = 0; i < r; i++) {
    val += log(n - i);
    val -= log(i + 1);
  }
  return val;
}
long long bin_search(long long key, long long A[], long long left,
                     long long right) {
  while (right >= left) {
    long long mid = left + (right - left) / 2;
    if (A[mid] == key)
      return mid;
    else if (A[mid] > key)
      right = mid - 1;
    else if (A[mid] < key)
      left = mid + 1;
  }
  return -1;
}
string bin_expression(long long n, long long dig) {
  string s = "";
  for (long long(i) = 0; (i) < (dig); (i)++) {
    s += to_string((n % 2));
    n /= 2;
  }
  reverse((s).begin(), (s).end());
  return s;
}
long long fact(long long n) {
  if (n == 0) return 1;
  return n * fact(n - 1);
}
long long fact_mod(long long n, long long mod) {
  if (n == 0) return 1;
  return n * fact_mod(n - 1, mod);
}
bool is_prime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
std::map<long long, long long> prime_factorization(long long n) {
  long long i = 2;
  std::map<long long, long long> table;
  while (i * i <= n) {
    while (n % i == 0) {
      table[i]++;
      n /= i;
    }
    i++;
  }
  if (n > 1) table[n] = 1;
  return table;
}
std::vector<long long> divisor_table(long long n) {
  std::vector<long long> table;
  long long i = 1;
  while (i * i <= n) {
    if (n % i == 0) {
      table.push_back(i);
      if (i * i != n) table.push_back(n / i);
    }
    i++;
  }
  sort((table).begin(), (table).end());
  return table;
}
long long next_combination(long long sub) {
  long long x = sub & -sub, y = sub + x;
  return (((sub & ~y) / x) >> 1) | y;
}
std::vector<long long> z_algorithm(string s) {
  long long n = s.length();
  std::vector<long long> res(n);
  res[0] = n;
  long long i1 = 1, i2 = 0;
  while (i1 < n) {
    while (i1 + i2 < n && s[i2] == s[i1 + i2]) ++i2;
    res[i1] = i2;
    if (i2 == 0) {
      ++i1;
      continue;
    }
    long long i3 = 1;
    while (i1 + i3 < n && i3 + res[i3] < i2) {
      res[i1 + i3] = res[i3];
      ++i3;
    }
    i1 += i3, i2 -= i3;
  }
  return res;
}
long long big_number_mod(string s, long long mod) {
  long long l = s.length();
  long long idx = 0;
  long long val = 0;
  long long tenth = 1;
  while (idx < l) {
    long long m = long long((s[l - 1 - idx])) - long long('0');
    val += (m * tenth) % mod;
    val %= mod;
    tenth *= 10;
    tenth %= mod;
    idx++;
  }
  return val;
}
long long big_number_compare(string s1, string s2) {
  if (s1.length() > s2.length())
    return 1;
  else if (s1.length() < s2.length())
    return -1;
  else if (s1 == s2)
    return 0;
  return 2 * (s1 > s2) - 1;
}
long long string_to_ll(string s) {
  long long l = s.length();
  long long idx = 0;
  long long val = 0;
  long long tenth = 1;
  while (idx < l) {
    long long m = long long((s[l - 1 - idx])) - long long('0');
    val += (m * tenth);
    tenth *= 10;
    idx++;
  }
  return val;
}
string reflected_string(string s) {
  string t, u;
  long long n = s.length();
  t = s;
  reverse((t).begin(), (t).end());
  u = t.substr((0), (n - 2) - (0) + 1) + s + t.substr((1), (n - 1) - (1) + 1);
  return u;
}
long double distance_between_point_line(point l_begin, point l_end, point p) {
  long long xl1 = l_begin.x, yl1 = l_begin.y;
  long long xl2 = l_end.x, yl2 = l_end.y;
  long long xp = p.x, yp = p.y;
  long long a = yl2 - yl1;
  long long b = -xl2 + xl1;
  long long c = -a * xl2 - b * yl2;
  return abs(long double(a * xp + b * yp + c)) /
         long double(sqrt(a * a + b * b));
}
bool is_cross(point l1_begin, point l1_end, point l2_begin, point l2_end) {
  long long x1 = l1_begin.x, y1 = l1_begin.y;
  long long x2 = l1_end.x, y2 = l1_end.y;
  long long x3 = l2_begin.x, y3 = l2_begin.y;
  long long x4 = l2_end.x, y4 = l2_end.y;
  long long val1 = (x1 - x2) * (y3 - y1) + (y1 - y2) * (x1 - x3);
  long long val2 = (x1 - x2) * (y4 - y1) + (y1 - y2) * (x1 - x4);
  long long val3 = (x3 - x4) * (y1 - y3) + (y3 - y4) * (x3 - x1);
  long long val4 = (x3 - x4) * (y2 - y3) + (y3 - y4) * (x3 - x2);
  return val1 * val2 < 0 && val3 * val4 < 0;
}
long double space_of_triangle(point p1, point p2, point p3) {
  long long x1 = p1.x, y1 = p1.y;
  long long x2 = p2.x, y2 = p2.y;
  long long x3 = p3.x, y3 = p3.y;
  long long v1 = x2 - x1;
  long long u1 = y2 - y1;
  long long v2 = x3 - x1;
  long long u2 = y3 - y1;
  long double s = long double(v1 * u2 - u1 * v2) / long double(2);
  return abs(s);
}
pair<point, long long> center_2det_of_3points(point p1, point p2, point p3) {
  long long x1 = p1.x, y1 = p1.y;
  long long x2 = p2.x, y2 = p2.y;
  long long x3 = p3.x, y3 = p3.y;
  long long c2x_2 = x2 + x1, c2y_2 = y2 + y1;
  long long c3x_2 = x3 + x1, c3y_2 = y3 + y1;
  long long b2y = x2 - x1, b2x = -y2 + y1;
  long long b3y = x3 - x1, b3x = -y3 + y1;
  long long x1_2 = c3x_2 * b3y - c3y_2 * b3x, y1_2 = c2x_2 * b2y - c2y_2 * b2x;
  long long det = -b3y * b2x + b3x * b2y;
  if (det == 0) return {{INF, INF}, det};
  long long cx_2det = -b2x * x1_2 + b3x * y1_2,
            cy_2det = -b2y * x1_2 + b3y * y1_2;
  return {{cx_2det, cy_2det}, det};
}
long long inversion_number(std::vector<long long> a, long long a_max) {
  BinaryIndexedTree bit(a_max + 1);
  long long val = 0;
  for (long long(i) = 0; (i) < (a.size()); (i)++) {
    val += i - bit.query(a[i] - 1);
    bit.update(a[i], 1);
  }
  return val;
}
template <typename T>
vector<T> compress(vector<T> v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
  return v;
}
template <typename T>
map<T, long long> dict(const vector<T>& v) {
  map<T, long long> d;
  for (long long(i) = 0; (i) < (v.size()); (i)++) d[v[i]] = i;
  return d;
}
std::vector<point> compress2D(std::vector<long long> xs,
                              std::vector<long long> ys) {
  long long n = xs.size();
  std::vector<long long> xcs = compress(xs), ycs = compress(ys);
  map<long long, long long> xd = dict(xcs), yd = dict(ycs);
  std::vector<point> ps(n);
  for (long long(i) = 0; (i) < (n); (i)++) xs[i] = xd[xs[i]], ys[i] = yd[ys[i]];
  for (long long(i) = 0; (i) < (n); (i)++) ps[i] = {xs[i], ys[i]};
  sort((ps).begin(), (ps).end());
  return ps;
}
void GaussJordanBitVector(std::vector<long long>& bs) {
  long long n = bs.size();
  long long rank = 0;
  long long j = 0;
  for (long long(i) = N_DIGITS - 1; (i) >= 0; (i)--) {
    for (j = rank; j < n; j++)
      if (bs[j] & (1LL << i)) break;
    if (j == n) continue;
    if (j > rank) bs[rank] ^= bs[j];
    for (j = rank + 1; j < n; j++) bs[j] = min(bs[j], bs[j] ^ bs[rank]);
    rank++;
  }
}
long long kruskal(vector<undirected_edge>& es, long long n_vertex) {
  sort((es).begin(), (es).end());
  UnionFind uf(n_vertex);
  long long min_cost = 0;
  for (long long(i) = 0; (i) < (es.size()); (i)++) {
    undirected_edge& e = es[i];
    if (!uf.is_same(e.from, e.to)) {
      min_cost += e.cost;
      uf.unite(e.from, e.to);
    }
  }
  return min_cost;
}
long long LongestIncreasedSequence(std::vector<long long>& v, long long n) {
  std::vector<long long> dp(n, INF);
  for (long long(i) = 0; (i) < (n); (i)++)
    *lower_bound((dp).begin(), (dp).end(), v[i]) = v[i];
  return lower_bound((dp).begin(), (dp).end(), INF) - dp.begin();
}
void dijkstra(long long start, std::vector<vector<edge>>& graph,
              std::vector<long long>& dist, std::vector<long long>& vertex_pre,
              bool trace = false) {
  priority_queue<std::pair<long long, long long>,
                 std::vector<std::pair<long long, long long>>,
                 greater<std::pair<long long, long long>>>
      edge_costs;
  long long n = graph.size();
  dist = std::vector<long long>(n, INF);
  if (trace) vertex_pre = std::vector<long long>(n, -1);
  dist[start] = 0;
  edge_costs.push(std::pair<long long, long long>(0, start));
  while (!edge_costs.empty()) {
    long long idx, cost;
    tie(cost, idx) = edge_costs.top();
    edge_costs.pop();
    if (dist[idx] < cost) continue;
    for (auto e : graph[idx]) {
      if (dist[e.to] > dist[idx] + e.cost) {
        dist[e.to] = dist[idx] + e.cost;
        if (trace) vertex_pre[e.to] = idx;
        edge_costs.push(std::pair<long long, long long>(dist[e.to], e.to));
      }
    }
  }
}
std::vector<long long> get_predecessor(long long g,
                                       std::vector<long long>& vertex_pre) {
  std::vector<long long> path;
  for (; g != -1; g = vertex_pre[g]) path.push_back(g);
  reverse((path).begin(), (path).end());
  return path;
}
void warshall_floyd(std::vector<std::vector<long long>>& dist) {
  long long n = dist.size();
  for (long long(k) = 0; (k) < (n); (k)++)
    for (long long(i) = 0; (i) < (n); (i)++)
      for (long long(j) = 0; (j) < (n); (j)++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
bool find_negative_cycle(long long n, long long goal,
                         std::vector<vector<edge>>& graph,
                         std::vector<long long>& dist) {
  for (long long(i) = 0; (i) < (n); (i)++)
    for (long long(v) = 0; (v) < (n); (v)++)
      for (long long(k) = 0; (k) < (graph[v].size()); (k)++) {
        edge e = graph[v][k];
        if (dist[e.to] != INF && dist[e.to] > dist[v] + e.cost) {
          dist[e.to] = -INF;
          if (goal == -1)
            return true;
          else if (goal == e.to)
            return true;
        }
      }
  return false;
}
bool bellman_ford(long long start, long long goal,
                  std::vector<vector<edge>>& graph,
                  std::vector<long long>& dist) {
  long long n = graph.size();
  dist = std::vector<long long>(n, INF);
  dist[start] = 0;
  for (long long(i) = 0; (i) < (n); (i)++)
    for (long long(v) = 0; (v) < (n); (v)++)
      for (long long(k) = 0; (k) < (graph[v].size()); (k)++) {
        edge e = graph[v][k];
        if (dist[v] != INF && dist[e.to] > dist[v] + e.cost)
          dist[e.to] = dist[v] + e.cost;
      }
  if (find_negative_cycle(n, goal, graph, dist)) return false;
  return true;
}
void read_graph(long long n_vertex, long long n_edges,
                std::vector<vector<edge>>& graph, long long cost = -1,
                long long directed = false, long long offset = -1) {
  graph.resize(n_vertex);
  for (long long(i) = 0; (i) < (n_edges); (i)++) {
    long long from, to, c = cost;
    if (cost == -1)
      cin >> (from) >> (to) >> (c);
    else
      cin >> (from) >> (to);
    from += offset, to += offset;
    graph[from].push_back({to, cost});
    if (!directed) graph[to].push_back({from, cost});
  }
}
void read_vector(long long n, std::vector<long long>& v, long long offset = 0) {
  v.resize(n);
  for (long long(i) = 0; (i) < (n); (i)++) {
    cin >> (v[i]);
    v[i] += offset;
  }
}
const long long MAX_N = 200005;
bool okay = false;
long long answer = 0;
string s;
long long n, m;
void solve() {
  std::vector<long long> v1, v2;
  read_vector(n, v1);
  read_vector(m, v2);
  std::vector<std::vector<long long>> dp(n + 1,
                                         std::vector<long long>(m + 1, 0));
  dp[0][0] = 1;
  for (long long(i) = 0; (i) < (n + 1); (i)++) dp[i][0] = 1;
  for (long long(i) = 0; (i) < (m + 1); (i)++) dp[0][i] = 1;
  for (long long(i1) = (1); (i1) < (n + 1); (i1)++)
    for (long long(i2) = (1); (i2) < (m + 1); (i2)++) {
      long long a = v1[i1 - 1], b = v2[i2 - 1];
      dp[i1][i2] = dp[i1 - 1][i2] + dp[i1][i2 - 1] - dp[i1 - 1][i2 - 1];
      if (a != b) continue;
      dp[i1][i2] += dp[i1 - 1][i2 - 1];
      (dp[i1][i2] += MOD) %= MOD;
    }
  cout << (dp[n][m]) << endl;
}
int main(void) {
  cin >> (n) >> (m);
  solve();
  return 0;
}
