Cola Robot

On the planet Galidun, people love drinking cola. In response, an enemy planet developed a cola robot and deployed it in city \(1\) of Galidun. This cola robot has three possible actions: it can stay in its current city, move to an adjacent city, or self-destruct. At the beginning, at \(t=0\), the robot is in city \(1\). Every second, if the robot is active, it randomly triggers exactly one of these actions. Note that if the robot chooses to self-destruct at some second, it will explode and no further actions will occur in the remaining seconds. Given the map of Galidun’s cities (represented as an undirected graph), determine the total number of distinct complete action sequences the robot may perform after \(t\) seconds. A complete action sequence is defined as:

• If the robot self-destructs at or before the \(t^{th}\) second, the sequence ends at the moment of self-destruction (and no actions occur in later seconds).
• If the robot never self-destructs in \(t\) seconds, then it performs an action (either staying or moving) at every second.

When the robot is in some city \(x\) with a set of adjacent cities \(N(x)\), the possibilities are:

\( \text{stay:} \quad 1 \) way (remains in \(x\)),

\( \text{move:} \quad |N(x)| \) ways (move to any adjacent city),

\( \text{self-destruct:} \quad 1 \) way (ends the sequence immediately).

Calculate the total number of distinct action plans the robot may execute over \(t\) seconds.

inputFormat

The first line contains three integers \(n\), \(m\) and \(t\) where \(n\) is the number of cities, \(m\) is the number of roads, and \(t\) is the total time in seconds.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating there is an undirected road between city \(u\) and city \(v\>.

You can assume that \(1 \leq u, v \leq n\) and the robot always starts at city \(1\) at \(t=0\).

outputFormat

Output a single integer, the total number of distinct complete action sequences that the cola robot can execute after \(t\) seconds following the rules described.

sample

1 0 1

2