#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 == ex.size ( ) ) {
        v[ tp ++ ] = aux ;
        return ;
    }
    for ( int i = 0 ; i <= cnt[ ex[ 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 ] ;

void mul ( int id1 , int id2 ) { 
    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 * pw[ id1 ][ i ][ t ] * pw[ id2 ][ t ][ j ] ) % MOD ;
                if ( ret[ i ][ j ] >= MOD ) { ret[ i ][ j ] -= MOD ; }
            }
        }
    }
}

ll qlen[ 152 ] , qret[ 152 ] ;

pair < ll , int > srt[ 152 ] ;
ll comb[ 256 ][ 256 ] ;
ll prec[ 256 ][ 256 ] ;


int ans[ 256 ] ;
int vec_prod[ 256 ] ;

void spec_mul ( int id ) {
    for ( int j = 0 ; j < tp ; ++ j ) {
        vec_prod[ j ] = 0 ;
        for ( int t = 0 ; t < tp ; ++ t ) {
            vec_prod[ j ] = ( vec_prod[ j ] + 1LL * ans[ t ] * pw[ id ][ t ][ 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 ( 0 ) ;
    comb[ 0 ][ 0 ] = 1 ;
    for ( int i = 1 ; i < 256 ; ++ i ) {
        for ( int j = 0 ; j < 256 ; ++ j ) {
            comb[ i ][ j ] = comb[ i - 1 ][ j ] ;
            if ( j > 0 ) { comb[ i ][ j ] = ( comb[ i ][ j ] + comb[ i - 1 ][ j - 1 ] ) % MOD ; }
        }
    }
    for ( int i = 0 ; i < 256 ; ++ i ) {
        prec[ i ][ 0 ] = 1 ;
        for ( int j = 1 ; j < 256 ; ++ j ) {
            prec[ i ][ j ] = ( prec[ i ][ j - 1 ] * i ) % MOD ;
        }
    }
    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 ] ] ;
                bad = ( bad * comb[ rem ][ v[ j ][ k ] ] ) % MOD ;
                bad = ( bad * prec[ ex[ k ] ][ v[ j ][ k ] ] ) % MOD ;
                tot = ( tot * comb[ foo ][ v[ j ][ k ] ] ) % MOD ;
                tot = ( tot * prec[ ex[ k ] ][ v[ j ][ k ] ] ) % MOD ;
            }
            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 ) {
            ans[ j ] = 0 ;
        }
        ans[ tp - 1 ] = 1 ;
        for ( int j = 60 ; j >= 0 ; -- j ) {
            if ( diff >= ( 1LL << j ) ) {
                spec_mul ( j ) ;
                for ( int t = 0 ; t < tp ; ++ t ) {
                    ans[ t ] = vec_prod[ t ] ;
                }
                diff -= ( 1LL << j ) ;
            }
        }
        for ( int t = 0 ; t < tp ; ++ t ) { 
            qret[ i ] = ( qret[ i ] + ans[ t ] ) % 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 ;
}