Source : 信息学奥赛一本通训练指导教程
Description

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

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

Input

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

Output

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

Sample Input
234
2
2 5
3 6
Sample Output
4