광선검 (어려운 버전)

한때 Galactic Senate에는 소요가 있었다. 수천 개의 태양계가 Republic을 떠나겠다는 의사를 선언했다. 하지만 걱정하지 말라! Master Heidi는 은하계의 평화를 회복한 Jedi Knights를 성공적으로 선발했다. 그러나 그녀는 악은 결코 잠들지 않으며, 언젠가 또 다른 Jedi Knights 무리를 골라야 할 때가 올 수도 있음을 알고 있다. 그녀는 그렇게 할 수 있는 선택지가 충분한지 확인하고 싶다.

n명의 Jedi Knights가 있으며, 각자는 m가지 색 중 하나인 광선검을 가지고 있다. 수 k가 주어질 때, 어떤 k명의 Jedi Knights가 가질 수 있는 k개 광선검 모음 중 색 구성으로 서로 다른 것의 수를 계산한다. 같은 색의 광선검을 가진 Jedi Knights는 서로 구별되지 않으며(중요한 것은 사람이 아니라 광선검의 색이다!), 순서도 중요하지 않다. 즉, 각 색의 광선검 개수로 이루어진 벡터(쉬운 버전과 중간 버전에서 주어진 것과 같은 벡터)가 서로 다를 때, 그리고 그럴 때에만 두 Jedi Knights 모음을 서로 다르다고 본다. 입력 수열에서 연속한 부분 구간뿐만 아니라 모든 부분집합을 센다. 답을 1009로 나눈 나머지를 출력한다.

입력의 첫 번째 줄에는 n (1 ≤ n ≤ 2·105), m (1 ≤ m ≤ n), 그리고 k (1 ≤ k ≤ n)가 주어진다. 두 번째 줄에는 차례로 이어지는 Jedi Knights의 광선검 색을 나타내는, 범위 {1, 2, ..., m}에 속하는 n개의 정수가 주어진다.

k개 광선검 모음 중 색 구성으로 서로 다른 것의 수를 1009로 나눈 나머지 하나를 출력한다.