牛牛得到了一堆神奇的恶魔果实，每个恶魔果实都给了牛牛一个改变数字的能力，可以把数字a变成数字b，现在牛牛有一个数字x，他想知道吃完这n个恶魔果实后，他可以把数字x变成多少种的数。 注：每一个恶魔果实的能力可以重复使用多次，当然也可以不用，存在相同能力的恶魔果实.

输入描述:

第一行输入一个正整数x(1≤x≤109)，和一个正整数n(1≤n≤106),接下来n行，每行一个a(0≤a≤9 )和一个b(1≤b≤9)。

输出描述:

表示可以变的数字种类数，答案对104+7取模