Circular Ball Passing

There are n players arranged in a circle and numbered from \(1\) to \(n\). Initially, the ball is with player \(1\). The ball is passed exactly \(m\) times. In each pass, the current holder must pass the ball to someone else (i.e. not to himself). In addition, there are \(k\) restrictions. Each restriction is a pair \((a,b)\) indicating that player \(a\) is not allowed to pass the ball to player \(b\).

Your task is to compute the number of ways that, after \(m\) passes, the ball returns to player \(1\), and output the answer modulo \(998244353\).

Note: All passes must obey both the rule that no player may pass to himself and the given \(k\) restrictions.

inputFormat

The input consists of multiple lines. The first line contains three integers \(n\), \(m\), and \(k\) separated by spaces. Each of the next \(k\) lines contains two integers \(a\) and \(b\), representing a restriction that player \(a\) cannot pass the ball to player \(b\).

\(1 \leq a, b \leq n,\) and \(a \neq b\).

outputFormat

Output one integer: the number of valid passing schemes modulo \(998244353\) such that after \(m\) passes, the ball returns to player \(1\).

sample

3 2 0

2