Problem: Tachibana Kanade likes Mapo Tofu very much. One day, the canteen cooked all kinds of tofu to sell, but not all tofu is Mapo Tofu, only those spicy enough can be called Mapo Tofu.

Each piece of tofu in the canteen is given a m-based number, all numbers are in the range [l, r] (l and r being m-based numbers), and for every m-based integer in the range [l, r], there exists a piece of tofu with that number.

To judge what tofu is Mapo Tofu, Tachibana Kanade chose n m-based number strings, and assigned a value to each string. If a string appears in the number of a tofu, the value of the string will be added to the value of that tofu. If a string appears multiple times, then the value is also added that many times. Initially the value of each tofu is zero.

Tachibana Kanade considers tofu with values no more than k to be Mapo Tofu. So now Tachibana Kanade wants to know, how many pieces of tofu are Mapo Tofu?

Input

The first line contains three integers n, m and k (1 ≤ n ≤ 200; 2 ≤ m ≤ 20; 1 ≤ k ≤ 500). Where n denotes the number of strings, m denotes the base used, and k denotes the limit of the value for Mapo Tofu.

The second line represents the number l. The first integer in the line is len (1 ≤ len ≤ 200), describing the length (number of digits in base m) of l. Then follow len integers a1, a2, ..., alen (0 ≤ ai < m; a1 > 0) separated by spaces, representing the digits of l, with a1 being the highest digit and alen being the lowest digit.

The third line represents the number r in the same format as l. It is guaranteed that 1 ≤ l ≤ r.

Then follow n lines, each line describing a number string. The i-th line contains the i-th number string and vi — the value of the i-th string (1 ≤ vi ≤ 200). All number strings are described in almost the same format as l, the only difference is number strings may contain necessary leading zeros (see the first example). The sum of the lengths of all number strings does not exceed 200.

Output

Output the number of pieces of Mapo Tofu modulo 1000000007 (109 + 7). The answer should be a decimal integer.

Examples

Input

2 10 1
1 1
3 1 0 0
1 1 1
1 0 1


Output

97


Input

2 10 12
2 5 9
6 6 3 5 4 9 7
2 0 6 1
3 6 7 2 1


Output

635439


Input

4 2 6
6 1 0 1 1 1 0
6 1 1 0 1 0 0
1 1 2
3 0 1 0 5
4 0 1 1 0 4
3 1 0 1 2


Output

2

Note

In the first sample, 10, 11 and 100 are the only three decimal numbers in [1, 100] with a value greater than 1. Here the value of 1 is 1 but not 2, since numbers cannot contain leading zeros and thus cannot be written as "01".

In the second sample, no numbers in the given interval have a value greater than 12.

In the third sample, 110000 and 110001 are the only two binary numbers in the given interval with a value no greater than 6.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chmax(T &m, const T &v) {
  if (v > m) return m = v, true;
  return false;
}
template <typename T>
bool chmin(T &m, const T &v) {
  if (v < m) return m = v, true;
  return false;
}
template <typename T>
bool chinc(T &v1, T &v2) {
  if (v1 > v2) return swap(v1, v2), true;
  return false;
}
template <typename T>
bool chdec(T &v1, T &v2) {
  if (v1 < v2) return swap(v1, v2), true;
  return false;
}
static const int HMAX32 = INT32_MAX / 2;
static const int HMIN32 = -HMAX32;
static const int64_t HMAX64 = INT64_MAX / 2;
static const int64_t HMIN64 = -HMAX64;
namespace fio {
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
struct Cg {
  inline char operator()() { return (char)getchar(); }
};
struct Cp {
  inline void operator()(char x) { putchar(x); }
};
struct Cpe {
  inline void operator()(char x) { putc(x, stderr); }
};
inline bool IS(char x) { return x == 10 || x == 13 || x == ' '; }
template <typename T>
struct Fr {
  T P;
  inline Fr &operator,(int &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  inline operator int() {
    int x;
    *this, x;
    return x;
  }
  inline Fr &operator,(long long &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  inline operator long long() {
    long long x;
    *this, x;
    return x;
  }
  inline Fr &operator,(char &x) {
    for (x = P(); IS(x); x = P()) continue;
    return *this;
  }
  inline operator char() {
    char x;
    *this, x;
    return x;
  }
  inline Fr &operator,(char *x) {
    char t = P();
    for (; IS(t); t = P()) continue;
    if (~t) {
      for (; !IS(t) && ~t; t = P()) *x++ = t;
    }
    *x++ = 0;
    return *this;
  }
  inline Fr &operator,(double &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  inline operator double() {
    double x;
    *this, x;
    return x;
  }
  inline Fr &operator,(long double &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  inline operator long double() {
    long double x;
    *this, x;
    return x;
  }
  inline Fr &operator,(unsigned int &x) {
    x = 0;
    char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  inline operator unsigned int() {
    unsigned int x;
    *this, x;
    return x;
  }
  inline Fr &operator,(unsigned long long &x) {
    x = 0;
    char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  inline operator unsigned long long() {
    unsigned long long x;
    *this, x;
    return x;
  }
};
template <typename T>
struct Fw {
  T P;
  inline Fw &operator,(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[10];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[10];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(unsigned int x) {
    if (x) {
      char s[10];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(unsigned int x) {
    if (x) {
      char s[10];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[19];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[19];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(unsigned long long x) {
    if (x) {
      char s[20];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(unsigned long long x) {
    if (x) {
      char s[20];
      int c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(char x) {
    P(x);
    return *this;
  }
  inline Fw &operator()(char x) {
    P(x);
    return *this;
  }
  inline Fw &operator,(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  inline Fw &operator()(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  inline Fw &operator()(double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
  inline Fw &operator()(long double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
};
}  // namespace fio
fio::Fw<fio::Cp> fout;
fio::Fw<fio::Cpe> ferr;
fio::Fr<fio::Cg> fin;
struct empty_type {};
template <typename Int>
Int gcd(Int a, Int b) {
  while (a != 0) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}
template <typename Int, typename RInt = Int>
Int lcm(Int a, Int b) {
  return a / gcd(a, b) * static_cast<RInt>(b);
}
template <typename Int, typename XInt>
Int extended_gcd(Int a, Int b, XInt &x, XInt &y) {
  static_assert(std::numeric_limits<XInt>::is_signed, "x, y must be signed");
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  Int g = extended_gcd(b, a % b, y, x);
  y -= (a / b) * x;
  return g;
}
template <typename Int, typename TInt = int64_t>
Int mul_mod(Int a, Int b, Int m) {
  TInt p = a;
  p = (p * b) % m;
  return (Int)p;
}
template <typename Int, typename PInt, typename TInt = int64_t>
Int pow_mod(Int a, PInt p, Int m) {
  Int r;
  a %= m;
  for (r = 1; p; p >>= 1) {
    if (p & 1) r = mul_mod(r, a, m);
    a = mul_mod(a, a, m);
  }
  return r;
}
template <typename Int, typename XInt = typename std::make_signed<Int>::type>
Int inv_mod(Int a, Int m) {
  XInt x, y;
  extended_gcd(a, m, x, y);
  if (x < 0) return x + m;
  return x;
}
template <typename Int>
Int addx_mod(Int u, Int v, Int m) {
  Int r = u + v;
  if (r >= m) r -= m;
  return r;
}
template <typename Int>
Int subx_mod(Int u, Int v, Int m) {
  Int r = u - v;
  if (r < 0) r += m;
  return r;
}
template <typename Int>
Int div_mod(Int u, Int v, Int m) {
  Int g = gcd(v, m);
  assert(u % g == 0);
  Int mm = m / g;
  return mul_mod(u / g, inv_mod(v / g, mm), mm);
}
template <typename Int>
Int div_pos_r(Int a, Int b, Int &r) {
  Int q = a / b;
  r = a % b;
  if (r < 0) {
    if (b < 0)
      q += 1, r -= b;
    else
      q -= 1, r += b;
  }
  return q;
}
template <int Alpha = 256, typename Attr = empty_type>
struct trie_node : Attr {
  int p = 0;
  int cs[Alpha] = {};
  int fail = 0;
  trie_node() { fill(begin(cs), end(cs), 0); }
};
template <int Alpha, typename Attr = empty_type>
using trie = vector<trie_node<Alpha, Attr>>;
template <int Alpha, typename Attr>
int trie_walk(trie<Alpha, Attr> &tr, int prev, int c, bool insert = false) {
  if (!insert || tr[prev].cs[c]) return tr[prev].cs[c];
  int cur = (int)tr.size();
  tr.push_back({});
  return tr[prev].cs[c] = cur;
}
template <int Alpha, typename Attr>
void ac_automaton_build(trie<Alpha, Attr> &tr) {
  deque<int> q;
  for (int c = 0; c < Alpha; ++c)
    if (tr[0].cs[c]) q.push_back(tr[0].cs[c]);
  while (!q.empty()) {
    int u = q.front();
    q.pop_front();
    for (int c = 0; c < Alpha; ++c) {
      int v = tr[u].cs[c];
      if (v == 0) continue;
      q.push_back(v);
      int m = tr[u].fail;
      while (m > 0 && tr[m].cs[c] == 0) m = tr[m].fail;
      tr[v].fail = tr[m].cs[c];
    }
  }
}
template <int Alpha, typename Attr>
int ac_automaton_transit(trie<Alpha, Attr> &tr, int u, int c) {
  while (u > 0 && tr[u].cs[c] == 0) u = tr[u].fail;
  return tr[u].cs[c];
}
struct Attr {
  int cost = 0;
};
static const int MOD = 1000000007;
int n, m, k;
trie<256, Attr> tr(1);
int trans[405][256];
int dp[205][405][505];
int solve_all(int tot, int d, int u, int cost) {
  assert(u == 0 && cost == 0);
  ;
  if (cost > k) return 0;
  if (d == tot) return 1;
  int ans = 0;
  for (int i = 0; i < m; ++i) {
    if (i == 0)
      (ans) = addx_mod((ans), (solve_all(tot, d + 1, u, cost)), MOD);
    else {
      int v = trans[u][i];
      int new_cost = cost + tr[v].cost;
      for (int rest_cost = 0, rest_costend = k - new_cost;
           rest_cost <= rest_costend; rest_cost++)
        (ans) = addx_mod((ans), (dp[tot - 1 - d][v][rest_cost]), MOD);
    }
  }
  return ans;
}
int solve(const vector<int> &num, int d, int u, int cost, bool zero) {
  assert(num[0] != 0);
  ;
  if (cost > k) return 0;
  if (d == (int)num.size()) return 1;
  int ans = 0;
  for (int i = 0; i < num[d]; ++i) {
    if (zero && i == 0) {
      assert(d == 0);
      (ans) =
          addx_mod((ans), (solve_all((int)num.size(), d + 1, u, cost)), MOD);
      ;
      continue;
    }
    int v = trans[u][i];
    int new_cost = cost + tr[v].cost;
    for (int rest_cost = 0, rest_costend = k - new_cost;
         rest_cost <= rest_costend; rest_cost++)
      (ans) = addx_mod((ans), (dp[num.size() - 1 - d][v][rest_cost]), MOD);
  }
  int i = num[d];
  int v = trans[u][i];
  int new_cost = cost + tr[v].cost;
  (ans) = addx_mod((ans), (solve(num, d + 1, v, new_cost, false)), MOD);
  return ans;
}
int main() {
  fin, n, m, k;
  int nl, nr;
  vector<int> ls, rs;
  fin, nl;
  ls.resize(nl);
  for (int i = 0, iend = nl; i < iend; i++) fin, ls[i];
  fin, nr;
  rs.resize(nr);
  for (int i = 0, iend = nr; i < iend; i++) fin, rs[i];
  for (int i = 0, iend = n; i < iend; i++) {
    int p = 0;
    int len;
    fin, len;
    for (int _ = 0, _end = len; _ < _end; _++) {
      int c;
      fin, c;
      p = trie_walk(tr, p, c, true);
    }
    int v;
    fin, v;
    tr[p].cost += v;
  }
  ac_automaton_build(tr);
  {
    deque<int> q = {0};
    while (!q.empty()) {
      int u = q.front();
      q.pop_front();
      for (int c = 0; c < m; ++c) {
        int v = tr[u].cs[c];
        if (v == 0) continue;
        q.push_back(v);
      }
      tr[u].cost += tr[tr[u].fail].cost;
    }
  }
  for (int i = 0, iend = (int)tr.size(); i < iend; i++)
    for (int c = 0, cend = m; c < cend; c++) {
      trans[i][c] = ac_automaton_transit(tr, i, c);
    }
  int nstate = (int)tr.size();
  assert(nstate < 400);
  for (int u = 0, uend = nstate; u < uend; u++) dp[0][u][0] = 1;
  for (int len = 1, lenend = nr + 1; len <= lenend; len++)
    for (int u = 0, uend = nstate; u < uend; u++)
      for (int cost = 0, costend = k; cost <= costend; cost++)
        for (int c = 0, cend = m; c < cend; c++) {
          int v = trans[u][c];
          int new_cost = cost - tr[v].cost;
          if (new_cost >= 0)
            (dp[len][u][cost]) =
                addx_mod((dp[len][u][cost]), (dp[len - 1][v][new_cost]), MOD);
        }
  int ans = 0;
  (ans) = addx_mod((ans), (solve(rs, 0, 0, 0, true)), MOD);
  (ans) = subx_mod((ans), (solve(ls, 0, 0, 0, true)), MOD);
  {
    int cost = 0;
    int p = 0;
    for (int i = 0; i < nl; ++i) {
      p = trans[p][ls[i]];
      cost += tr[p].cost;
    }
    if (cost <= k) (ans) = addx_mod((ans), (1), MOD);
  }
  fout, ans, "\n";
  return 0;
}