The last wizard

The last wizard in the world, Jaeui, is close to his final moment. Jaeui understands every natural phenomenon and carries vast mana in his body, yet against an incurable disease of unknown cause he could do nothing. Writhing in pain, Jaeui kept preparing an arrangement that stops magic from dying out in the world, and only the finishing touch is left. His closest friend Taehyun receives this arrangement.

Jaeui numbered the 10 kinds of mana he considered essential from 0 to 9 and made them trainable for Taehyun. Taehyun is an ordinary person, so he holds amount 1 of each of the 10 kinds of mana.

One training session has $N$ ways for mana to increase. Number the ways from 1 to $N$. Way $i$ happens with probability $P_i / A$, and then each of the 10 kinds of mana grows by a fixed amount. The sum of all $P_i$ can be smaller than $A$, so a session can leave every mana unchanged. The result of one session is independent of the results of the other sessions.

Jaeui takes the product of the amounts of all 10 kinds of mana after training ends as the strength of magic. As the last step of the arrangement, Jaeui wants the expected strength of magic after $T$ training sessions. He handed the work to you, a friend he is not close to. Help Jaeui.

The first line contains three natural numbers $T$, $N$, $A$ separated by spaces. ($1 \le T \le 10^{12}$, $1 \le N \le 10\,000$, $1 \le A \le 10^9$)

Each of the next $N$ lines contains 11 integers separated by spaces. The first integer is $P_i$, and the remaining 10 are the increase of mana 0, the increase of mana 1, ..., the increase of mana 9, in that order. Every $P_i$ is at least 0 and the sum of all $P_i$ is at most $A$. Each increase is an integer between 0 and 9,999, and at least one of the 10 increases on a line is 1 or more.

Multiplying the expected product of the amounts of all 10 kinds of mana after $T$ training sessions by $A^T$ gives an integer. Print that integer modulo 1,000,000,007 on the first line.