牛牛的数字
题号：NC21369
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛牛最喜欢的数字是n，他还有一系列的特殊的数，这些数是唯一的，他想要知道这些数中有多少个子集的乘积等于n，而且子集内的数两两互质

输入描述:

第一行输入两个整数n,m (2 ≤ n ≤ 1018, 1 ≤ m ≤ 50)
接下来m行每行输入一行字符串 
每行字符串长度为1到50之间，包括数字'0'-'9'以及空格
将m行字符串连接起来可以组成牛牛的特殊数列
每个数字在1到109之间,最多有500个特殊的数
(推荐使用c++的istringstream 流来方便的转换类型)

输出描述:

输出一个整数
示例1

输入

复制 
12 1
4 2 5 6 3

输出

复制 
1
示例2

输入

复制 
42 1
1 2 3 4 5 6 7 13 14 21 42

输出

复制 
10
示例3

输入

复制 
1337 1
1 13 42 666 2674

输出

复制 
0
示例4

输入

复制 
1073741824 4
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 1
6384 32768 65536 131072 262144 524288 1048576 2097
152 4194304 8388608 16777216 33554432 67108864 134
217728 268435456 536870912

输出

复制 
0
示例5

输入

复制 
7420738134810 7
435 625199055 4199 33263 17 222870 284870433 72093
2379 7 11 31 247110827 23 1771 81809 851968487 13 
476379795 1001 5 435274114 38264554 7429 239906525
 3 227183706 887045414 606786670 3795 797605175 29
 30 747186719 19 2 562347843 74 2294 588002688 743
6429 703 591740547 36657492 37 444178205 1002001 2
17626404

输出

复制 
110

说明

注意样例5：第二行字符串最后有个空格

备注:

子任务1: n <= 1000
子任务2: n <= 109
子任务3: 无限制