UOJ Logo

NOI.AC

#56. word

统计

题目描述

我想让你告诉我一个数字串……

这个串的长度必须是 $n$,并且每一位都是 1 到 $k$ 的数字。($1 \leq k \leq 9$)

我还会给你 $m$ 条“禁止规则”。对于第 $i$ 条规则,我会给你两个数字 $a_i$ 与 $b_i$,表示数字 $a_i$ 禁止出现在数字 $b_i$ 之前。

现在,我要问你以下两个问题:

  • 一共有多少种你可以告诉我的数字串?
  • 如果把数字串看成一个整数,那么所有可能的数字串作为整数的和是多少?

输入格式

从标准输入读入数据。

第一行输入三个空格隔开的整数 $n, m, k$。

接下来 $m$ 行,每行输入两个空格隔开的整数,其中第 $i$ 行输入的整数为 $a_i, b_i$。($1 \leq a_i, b_i \leq k$)

输出格式

输出到标准输出。

输出两行,每行一个整数,分别对应每个问题的答案。

样例

输入

4 4 3
1 1
1 2
2 2
3 1

输出

7
19020

解释

符合条件的数字串共有 7 个,分别为:1333,2133,2333,3233,3323,3332,3333。

如果把它们视为整数,则求和为19020。

数据规模

对于测试点 1,保证 $n = 1$。

对于测试点 2,3,4,保证 $n \leq 6$。

对于测试点 5,6,保证 $n \leq 50$。

对于测试点 7,8,保证 $n \leq 200$。

对于所有编号为奇数的测试点,保证 $m = 0$。

对于全部数据,保证 $1 \leq n \leq 500, 0 \leq m \leq 100$。