#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 ( ) ;
    }
}

vector < vector < int > > ori ;
vector < vector < int > > pw[ 61 ] ;
vector < vector < int > > ret , ans ;

void mul ( vector < vector < int > > &hh1 , vector < vector < int > > &hh2 ) {
    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 ) {
                ret[ i ][ j ] += ( 1LL * hh1[ i ][ t ] * hh2[ t ][ j ] ) % MOD ;
                if ( ret[ i ][ j ] >= MOD ) { ret[ i ][ j ] -= MOD ; }
            }
        }
    }
}

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 ( ) ;
    ori.resize ( tp ) ;

    for ( int i = 0 ; i < tp ; ++ i ) {
        ori[ i ].resize ( tp , 0 ) ;
        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 ; }
        }
    }

    ans.resize ( tp ) ;
    ret.resize ( tp ) ;
    for ( int i = 0 ; i < tp ; ++ i ) {
        ans[ i ].resize ( tp , 0 ) ;
        ret[ i ].resize ( tp , 0 ) ;
    }
    pw[ 0 ].assign ( ori.begin ( ) , ori.end ( ) ) ;
    for ( int i = 1 ; i <= 60 ; ++ i ) {
        mul ( pw[ i - 1 ] , pw[ i - 1 ] ) ;
        pw[ i ].assign ( ret.begin ( ) , ret.end ( ) ) ;
    }
    for ( int i = 0 ; i < tp ; ++ i ) {
        for ( int j = 0 ; j < tp ; ++ j ) {
            assert ( ori[ i ][ j ] == pw[ 0 ][ i ][ j ] ) ;
        }
    }
    while ( q -- ) {
        ll wh ; cin >> wh ;
        int hh = 0 ;
        if ( wh == 1 ) { ++ hh ; }
        for ( int i = 0 ; i < tp ; ++ i ) {
            for ( int j = 0 ; j < tp ; ++ j ) {
                if ( i == j ) { ans[ i ][ j ] = 1 ; }
                else { ans[ i ][ j ] = 0 ; }
            }
        }
        for ( int i = 60 ; i >= 0 ; -- i ) {
            if ( wh >= ( 1LL << i ) ) {
                mul ( ans , pw[ i ] ) ;
                ans.assign ( ret.begin ( ) , ret.end ( ) ) ;
                wh -= ( 1LL << i ) ;
            }
        }
        for ( int i = 0 ; i < tp ; ++ i ) {
            hh = ( hh + ans[ tp - 1 ][ i ] ) % MOD ;
        }
        cout << hh << "\n" ;
    }
}

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