恶魔果实之力

暖心签到题。

QQQQQQQ的银行卡余额为一个正整数n，现在他通过某种py交易获得了m个恶魔果实，恶魔果实给予他的技能十分强大，每一个恶魔果实给予的技能是可以让他把数字x变成数字y，靠着这些恶魔果实给予的技能，他可以把银行卡余额无限次的变多，每次要没钱的时候，都操作一波，钱又变回来了。现在他想知道，通过这些恶魔果实的能力，可以把银行卡的余额变成的种类数有多少。  

恶魔果实给予的技能可能一模一样   每个技能可以不使用，也可以使用无限次  也就是  Σ(所有技能使用次数)为 0 ~ +∞

多组输入。(少于1000组 极限数据少于20组 标程32ms  所以随便写 不会T  T了的话我服你。。。）

第一行输入一个正整数n（无前导0），和一个正整数m   

接下来m行，每行一个x和一个y

其中  n≤2³³   m≤20      0≤x≤9    1≤y≤9

每组输入对应一行输出，答案可能很大，请将答案取模2³²后输出 

456 3
5 6
4 5
4 5
111 1
1 2

6
8
hint：
456  556  656  466  566  666
111 112 121 122 211 212 221 222