@staticmethod
def d():
    (n, m, *f) = map(int, sys.stdin.read().split())
    prev = ([0] * (n + 1))
    tmp = defaultdict(int)
    for i in range(n):
        prev[(i + 1)] = tmp[f[i]]
        tmp[f[i]] = (i + 1)
    dp = ([0] * (n + 1))
    dp[0] = 1
    (l, s) = (0, dp[0])
    for i in range(1, (n + 1)):
        while (l < prev[i]):
            s = ((s - dp[l]) % MOD)
            l += 1
        dp[i] = s
        s = ((s + dp[i]) % MOD)
    print(dp[n])
@staticmethod
def d():
    (n, m, *f) = map(int, sys.stdin.read().split())
    prev = ([0] * (n + 1))
    tmp = defaultdict(int)
    for i in range(n):
        prev[(i + 1)] = tmp[f[i]]
        tmp[f[i]] = (i + 1)
    dp = ([0] * (n + 1))
    dp[0] = 1
    (l, s) = (0, dp[0])
    for i in range(1, (n + 1)):
        while (l < prev[i]):
            s = ((s - dp[l]) % MOD)
            l += 1
        dp[i] = s
        s = ((s + dp[i]) % MOD)
    print(dp[n])