题目描述

现请你构造一个长度为 $n$ 位的数字，数字的每一位都是 $1$ 到 $k$ 的数码，且满足给定的 $m$ 条 限制规则： 其中第 $i$ 条规则，包含两个参数 $x_i$ 与 $y_i$，表示数码 $x_i$ 禁止出现在数码 $y_i$ 之前。

请问，按如上构造方法，共能构造出多少个合法的数字？这些合法数字的和是多少？

输入格式

输入第一行，三个正整数，分别表示 $n,m,k$ 接下来 $m$ 行， 每行两个正整数 $x_i,y_i$，表示第 $i$ 条限制的两个参数。

输出格式

输出共两行： 第一行：一个正整数表示所有合法数字的个数 第二行：这些合法数字的和

4 4 3
1 2
2 2 
3 1
1 1

7
19020

样例解释 1

符合条件的数字共有 7 个，分别为：1333，2133，2333，3233，3323，3332，3333

数据范围

• 对于 $40\%$ 的数据，$1 \leq n \leq 6$
• 对于 $60\%$ 的数据，$1 \leq n \leq 50$
• 对于 $80\%$ 的数据，$1 \leq n \leq 200$
• 对于 $100\%$ 的数据，$1 \leq n \leq 500$ ， $1 \leq m \leq 50$，$1 \leq k \leq 9$