마지막 마법사

세상의 마지막 마법사 재의에게 마지막 순간이 다가온다. 온갖 자연현상을 이해하고 광대한 마나를 몸에 담은 대마법사 재의도 원인 모를 불치병 앞에서는 아무 방법이 없었다. 재의는 고통에 몸부림치면서도 세상에서 마법의 맥이 끊기지 않도록 안배를 준비해 왔고, 이제 마무리만 남았다. 이 안배는 그의 가장 친한 친구인 태현이가 받는다.

재의는 반드시 수련해야 한다고 여긴 마나 10가지에 0번부터 9번까지 번호를 붙여 태현이가 수련할 수 있게 했다. 평범한 사람인 태현이는 마나 10가지를 각각 1의 양만큼 지니고 있다.

수련을 한 번 하면 마나가 늘어나는 경우가 $N$가지 있다. 각 경우에 1번부터 $N$번까지 번호를 붙이면 $i$번째 경우는 $P_i / A$의 확률로 일어나고, 그때 마나 10가지가 정해진 양만큼 늘어난다. 모든 $P_i$의 합이 $A$보다 작을 수 있다. 즉 수련을 해도 마나가 전혀 늘지 않을 수 있다. 수련 한 번의 결과는 다른 수련의 결과와 독립이다.

재의는 수련이 모두 끝난 뒤 마나 10가지의 양을 모두 곱한 값을 마법의 강한 정도로 본다. 안배의 마지막 단계로 재의는 수련을 $T$번 했을 때 마법의 강한 정도의 기댓값을 구하려 한다. 재의는 이 일을 친하지 않은 친구인 당신에게 맡겼다. 재의를 도와주자.

첫 줄에 자연수 $T$, $N$, $A$가 공백으로 구분되어 주어진다. ($1 \le T \le 10^{12}$, $1 \le N \le 10\,000$, $1 \le A \le 10^9$)

다음 $N$개의 줄에는 각각 정수 11개가 공백으로 구분되어 주어진다. 첫 번째 정수는 $P_i$이고, 이어지는 10개는 차례로 0번 마나의 증가량, 1번 마나의 증가량, ..., 9번 마나의 증가량이다. 모든 $P_i$는 0 이상이고 그 합은 $A$ 이하이다. 증가량은 0 이상 9,999 이하의 정수이며, 한 줄에 놓인 증가량 10개 중 적어도 하나는 1 이상이다.

수련을 $T$번 마친 뒤 마나 10가지의 양을 모두 곱한 값의 기댓값에 $A^T$를 곱하면 정수가 된다. 그 정수를 1,000,000,007로 나눈 나머지를 첫 줄에 출력한다.