10912번 - The last wizard

이 세상의 마지막 마법사 재의에게 마지막 순간이 다가오려고 하고 있다. 온갖 자연현상을 이해하고 광대한 마나를 몸에 담아 인간을 초월한 대마법사인 재의도 원인을 알 수 없는 불치병에 대해서는 손을 쓸 수 있는 방법이 없었다. 고통에 몸부림치면서도 재의는 세상에 마법의 맥이 끊어지지 않게 하기 위한 안배를 준비해 왔고, 이제는 마치기 직전에 왔다. 이 안배는 그의 가장 친한 친구인 태현이가 받게 될 것이다.

재의는 필수적으로 수련해야 한다고 여긴 10가지의 마나(0번에서 9번이라고 이름 붙였다.)를 수련할 수 있도록 할 수 있게 했다. 평범한 사람인 태현이는 이 10가지의 마나를 모두 1의 양만큼 가지고 있다. 마나가 증가하게 되는 경우는 총 N 가지 있는데, 각 경우를 1에서 N까지의 번호를 붙이면 P_i / A의 확률로 i 번째 경우가 걸린다. ΣP_i가 A보다 작을 수도 있다. 즉 수련을 해도 마나가 증가하지 않을 수도 있다. 재의는 수련이 끝난 후에 모든 마나의 양을 곱한 값이 마법의 강한 정도라고 생각하고 있다.

안배를 끝내는 마지막 단계로 재의는 수련을 T 번 했을 때 마법의 강한 정도의 기댓값을 구해보고자 한다. 이를 위해 재의는 친하지 않은 친구인 당신에게 이 일을 맡겼다. 불쌍한 재의를 도와주자.

첫 번째 줄에 세 자연수 T(1 ≤ T ≤ 10¹²), N(1 ≤ N ≤ 10,000), A(1 ≤ A ≤ 10⁹)이 공백으로 구분되어 주어진다.

다음 N 개의 줄의 각 줄에는 11개의 정수가 공백으로 구분되어 주어지는데, 가장 첫 번째 정수는 P_i를 의미하는 정수이고, 나머지 10개의 정수는 각각 0번 마나의 증가량, 1번 마나의 증가량, ..., 9번 마나의 증가량을 의미한다. 모든 P_i의 합이 A 이하임은 보장되며, 마나의 증가량은 0 이상 9,999 이하의 정수로 적어도 하나는 1 이상이다.

첫 번째 줄에 T번의 수련을 마치고 난 후 10가지 마나의 양을 모두 곱한 값의 기댓값을 출력한다. 이 값에 A^T를 곱한 값은 정수가 되는 것이 보장되므로, A^T를 곱한 후 1,000,000,007로 나눈 나머지를 출력한다.