P3515

产生数(Produce)

时间限制: 1s 内存限制: 64MB 简单 通过 50.31%
描述

  给出一个整数 n(n≤2000)n(n≤2000) 和 kk 个变换规则(k≤15)(k≤15)。规则:
  (1) 11 个数字可以变换成另 11 个数字;
  (2) 规则中,右边的数字不能为零。
  例如:n=234,k=2n=234,k=2 规则为2→5,3→62 \rightarrow 5,3 \rightarrow 6

  上面的整数 234234 经过变换后可能产生出的整数为(包括原数)234234,534534,264264,564564 共 44 种不同的产生数。
  求经过任意次的变换(00 次或多次),能产生出多少个不同的整数。仅要求输出不同整数个数。

输入

  nkx1y1x2y2⋯⋯xnyn\begin{matrix}n & \\ k \\ x_1 & y_1 \\ x_2 &y_2 \\ \cdots & \cdots \\ x_n & y_n \end{matrix}

输出

格式为一个整数(满足条件的整数个数)。

样例输入
234
2
2 5
3 6
样例输出
4