B. Daily Reorganisation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Every morning at 9 AM sharp, your manager posts a Slack message: "Good morning team! We're restructuring again to align with our strategic vision!!"

Here at MegaCorp Inc, we don't have departments; we have $$$m$$$ dynamic Synergy Hubs numbered $$$1$$$ to $$$m$$$. You are starting your journey today in Hub $$$1$$$, which, as you recall, brought down production twice in the last month.

To navigate this fluid ecosystem, we transition using one of our $$$k$$$ Key Strategic Methodologies (e.g., Agile Transformation, Lean Optimisation, Synergistic Disruption). In other words, there are several forms you can file to exit/enter hubs, which can be categorized into $$$k$$$ methodologies. Who comes up with this stuff?

Management maintains meticulous transparency. Each Hub $$$i \in \{1, \dots, m\}$$$ has its own unique set of forms for each Methodology $$$j \in \{1, \dots, k\}$$$, which for some Hub $$$i$$$ can be split as follows.

There are $$$c_{i,j}$$$ unique Departure Forms of type $$$j$$$ (like Agile Exit Protocol A-1).

Similarly, there are $$$c_{i,j}$$$ unique Onboarding Forms of type $$$j$$$ for that Hub.

Management assures us that the number of ways to leave a Hub using a methodology is always the same as the number of ways to join it using that same methodology. It's about Process Symmetry.

Every day, you must execute a "Strategic Realignment." This consists of two steps:

  • LEAVE your current Hub. You must file one of its available Departure Forms.
  • JOIN a new Hub. You must file one of the Onboarding Forms for the Hub you are moving to. (Note: You are allowed to "re-org" right back into the same Hub. This is called "Re-committing to your Core Mission.")
Now there is a new rule from corporate to "Maximise Innovation":

The Methodology type you use to leave a Hub CANNOT be the same as the Methodology type you use to join your new Hub.

As your manager explained: "If you exit with Synergy, you must enter with Lean. We can't have you leaving and joining via Agile! Think of the paradigm shifts!"

Your Task

Your manager, holding his morning coffee, now turns to you. "For our Future-State Planning meeting, I need a simple number."

How many distinct sequences of forms could you possibly file over exactly $$$d$$$ days?

You look at the clock. It's 9:05 AM. It's going to be a long week.

Input

The first line contains three integers $$$1 \leq m \leq 10^4$$$, $$$1 \leq k \leq 40$$$ and $$$1 \leq d \leq 10^6$$$ — the number of hubs, the number of methodologies, and the number of days.

The $$$i$$$-th line of the next $$$m$$$ lines contains $$$k$$$ integers $$$c_{i,1}, c_{i,2}, \dots, c_{i,k}$$$ ($$$0 \leq c_{i,j} \leq 10^9$$$), where $$$c_{i,j}$$$ is the number of forms to enter/exit hub $$$i$$$ with methodology $$$j$$$.

It is guaranteed that for every Hub, there are the same number of Departure and Onboarding Forms.

You always start in Hub 1.

Output

Print a single integer — the total number of distinct sequences of daily exit and entry forms possible after $$$d$$$ days, modulo $$$10^9 + 7$$$.

Examples
Input
2 3 1
1 0 2
2 1 2
Output
13
Input
2 2 2
2 2
0 3
Output
148