#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7 ;

ull modmul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}


bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
	    s = __builtin_ctzll(n-1), d = n >> s;
	for (ull a : A) {   // ^ count trailing zeroes
		ull p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}


ull pollard(ull n) {
	auto f = [n](ull x) { return modmul(x, x, n) + 1; };
	ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
	while (t++ % 40 || __gcd(prd, n) == 1) {
		if (x == y) x = ++i, y = f(x);
		if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}
vector<ull> factor(ull n) {
	if (n == 1) return {};
	if (isPrime(n)) return {n};
	ull x = pollard(n);
	auto l = factor(x), r = factor(n / x);
	l.insert(l.end(), r.begin ( ) , r.end ( ) );
	return l;
}

ull n ;
int q ;
map < ull , int > w ;
int cnt[ 60 ] ;
int tp = 0 ;
vector < int > v[ 500 ] ;
vector < int > aux ;
vector < int > ex ;

void rec ( int pos ) {
    if ( pos == 60 ) {
        v[ tp ++ ] = aux ;
        return ;
    }
    if ( cnt[ pos ] == 0 ) {
        rec ( pos + 1 ) ;
        return ;
    }
    for ( int i = 0 ; i <= cnt[ pos ] ; ++ i ) {
        aux.push_back ( i ) ;
        rec ( pos + 1 ) ;
        aux.pop_back ( ) ;
    }
}
int ori[ 256 ][ 256 ] ;
int pw[ 61 ][ 256 ][ 256 ] ;
int ret[ 256 ][ 256 ] , ans[ 256 ][ 256 ] ;

void mul ( int type , int id ) { 
    for ( int i = 0 ; i < tp ; ++ i ) {
        for ( int j = 0 ; j < tp ; ++ j ) {
            ret[ i ][ j ] = 0 ;
            for ( int t = 0 ; t < tp ; ++ t ) {
                if ( type == -1 ) { ret[ i ][ j ] += ( 1LL * ans[ i ][ t ] * pw[ id ][ t ][ j ] ) % MOD ; }
                else { ret[ i ][ j ] += ( 1LL * pw[ type ][ i ][ t ] * pw[ id ][ t ][ j ] ) % MOD ; }
                if ( ret[ i ][ j ] >= MOD ) { ret[ i ][ j ] -= MOD ; }
            }
        }
    }
}

ll qlen[ 152 ] , qret[ 152 ] ;

pair < ll , int > srt[ 152 ] ;

void solve ( ) {
    cin >> n >> q ;
    vector < ull > divs = factor ( n ) ;
    for ( auto x : divs ) {
        ++ w[ x ] ;
    }
    for ( auto e : w ) {
        ++ cnt[ e.se ] ;
    }
    for ( int i = 0 ; i <= 60 ; ++ i ) {
        if ( cnt[ i ] > 0 ) { ex.push_back ( i ) ; }
    }
    rec ( 1 ) ;
    int sz = v[ 0 ].size ( ) ;
    for ( int i = 0 ; i < tp ; ++ i ) {
        for ( int j = 0 ; j < tp ; ++ j ) {
            ll bad = 1 , tot = 1 ;
            for ( int k = 0 ; k < sz ; ++ k ) {
                ll rem = cnt[ ex[ k ] ] - v[ i ][ k ] , foo = cnt[ ex[ k ] ] ;
                for ( int ctr = 0 ; ctr < v[ j ][ k ] ; ++ ctr ) {
                    bad = ( bad * ( rem -- ) ) ;
                    tot = ( tot * ( foo -- ) ) ;
                    bad = bad * ( ex[ k ] ) ;
                    tot = tot * ( ex[ k ] ) ;
                }
                for ( int ctr = 0 ; ctr < v[ j ][ k ] ; ++ ctr ) {
                    bad = ( bad / ( ctr + 1 ) ) ;
                    tot = ( tot / ( ctr + 1 ) ) ;
                }
            }
            ori[ i ][ j ] = ( tot - bad ) % MOD ;
            if ( i == 0 || j == 0 ) { ori[ i ][ j ] = 0 ; }
        }
    }
    for ( int i = 0 ; i < tp ; ++ i ) {
        for ( int j = 0 ; j < tp ; ++ j ) {
            pw[ 0 ][ i ][ j ] = ori[ i ][ j ] ;
        }
    }
    for ( int i = 1 ; i <= 60 ; ++ i ) {
        mul ( i - 1 , i - 1 ) ;
        for ( int j = 0 ; j < tp ; ++ j ) {
            for ( int t = 0 ; t < tp ; ++ t ) {
                pw[ i ][ j ][ t ] = ret[ j ][ t ] ;
            }
        }
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        cin >> qlen[ i ] ;
        ll diff = qlen[ i ] ;
        for ( int j = 0 ; j < tp ; ++ j ) {
            for ( int t = 0 ; t < tp ; ++ t ) {
                if ( j == t ) { ans[ j ][ t ] = 1 ; }
                else { ans[ j ][ t ] = 0 ; }
            }
        }
        for ( int j = 60 ; j >= 0 ; -- j ) {
            if ( diff >= ( 1LL << j ) ) {
                mul ( -1 , j ) ;
                for ( int t = 0 ; t < tp ; ++ t ) {
                    for ( int z = 0 ; z < tp ; ++ z ) {
                        ans[ t ][ z ] = ret[ t ][ z ] ;
                    }
                }
                diff -= ( 1LL << j ) ;
            }
        }
        for ( int j = 0 ; j < tp ; ++ j ) {
            qret[ i ] = ( qret[ i ] + ans[ tp - 1 ][ j ] ) % MOD ;
        }
        if ( qlen[ i ] == 1 ) { ++ qret[ i ] ; }
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        cout << qret[ i ] << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}