#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

const int MAXN = 100000;
struct Trie {
    int next[MAXN][2], fail[MAXN];
    bool end[MAXN];
    int L,root;

    int newNode() {
        for (int i = 0; i < 2; i++)
            next[L][i] = -1;
        end[L] = false;
        return L++;
    }

    void init() {
        L = 0;
        root = newNode();
    }

    void insert(int s[], int id, int n) {
        int now = root;
        for (int i = 0; i < n; i++) {
            if (next[now][s[i] == id] == -1)
                next[now][s[i] == id] = newNode();
            now = next[now][s[i] == id];
        }
        end[now] = true;
    }

    void build() {
        queue<int> Q;
        for (int i = 0; i < 2; i++)
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                Q.push(next[root][i]);
            }
        while (!Q.empty()) {
            int now = Q.front();
            Q.pop();
            end[now] |= end[fail[now]];
            for (int i = 0; i < 2; i++)
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }
    }
};
Trie xiaodao[25];
int n, m, ha, hb;
int a[MAXN], b[MAXN], c[MAXN];
int pos[25][25];

bool check(int now, int last) {
    if (now == ha)  return true;
    for (int i = last + 1; i < hb; i++)
        if (xiaodao[i].end[pos[now][i]])
            if (check(now + 1, i))
                return true;
    return false;
}
int main() {
    while (scanf("%d%d%d", &n, &m, &ha) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            a[i]--;
            c[i] = a[i];
        }
        sort(c, c + n);
        ha = unique(c, c + n) - c;
        for (int i = 0; i < n; i++)
            a[i] = lower_bound(c, c + ha, a[i]) - c;

        for (int i = 0; i < m; i++) {
            scanf("%d", &b[i]);
            b[i]--;
            c[i] = b[i];
        }
        sort(c, c + m);
        hb = unique(c, c + m) - c;
        for (int i = 0; i < m; i++)
            b[i] = lower_bound(c, c + hb, b[i]) - c;

        for (int i = 0; i < hb; i++) {
            xiaodao[i].init();
            xiaodao[i].insert(b, i, m);
            xiaodao[i].build();
        }
        memset(pos, 0, sizeof(pos));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int aaa = 0; aaa < ha; aaa++)
                for (int bbb = 0; bbb < hb; bbb++)
                    pos[aaa][bbb] = xiaodao[bbb].next[pos[aaa][bbb]][aaa == a[i]];
            if (check(0, -1)) {
                ans++;
                memset(pos, 0, sizeof(pos));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}