MOD=1000000007
def power(no,p):
    if(p==0):
        return 1
    if(p==1):
        return no
    if(p&1==1):
        ans=power(no,p/2)
        return (((ans*ans)%MOD)*no)%MOD
    ans=power(no,p/2)
    return (ans*ans)%MOD
t=(int)(raw_input())
q=[0 for i in range(110)]
p=[0 for i in range(110)]
arr=[0 for i in range(110)]
while(t>0):
    v,n=map(int,raw_input().split()) 
    p[0],p[1],a0,b0,c0,m0=map(int,raw_input().split())
    q[0],q[1],a1,b1,c1,m1=map(int,raw_input().split())
    arr[0]=p[0]*m1+q[0]
    arr[1]=p[1]*m1+q[1]
    for i in range(2,n):
        p[i]=(a0*a0*p[i-1]+b0*p[i-2]+c0)%m0
        q[i]=(a1*a1*q[i-1]+b1*q[i-2]+c1)%m1
        arr[i]=(p[i]*m1+q[i])
    temp=1
    for i in range(0,n):
        temp*=arr[i]
        temp%=(MOD-1)
        if(temp==0):
            break;
    if(v%MOD==0)and(temp!=0):
        print(0)
    elif(temp==0):
        print(1)
    else:
        print (power(v,temp))
    t-=1 

TU9EPTEwMDAwMDAwMDcKZGVmIHBvd2VyKG5vLHApOgogICAgaWYocD09MCk6CiAgICAgICAgcmV0dXJuIDEKICAgIGlmKHA9PTEpOgogICAgICAgIHJldHVybiBubwogICAgaWYocCYxPT0xKToKICAgICAgICBhbnM9cG93ZXIobm8scC8yKQogICAgICAgIHJldHVybiAoKChhbnMqYW5zKSVNT0QpKm5vKSVNT0QKICAgIGFucz1wb3dlcihubyxwLzIpCiAgICByZXR1cm4gKGFucyphbnMpJU1PRAp0PShpbnQpKHJhd19pbnB1dCgpKQpxPVswIGZvciBpIGluIHJhbmdlKDExMCldCnA9WzAgZm9yIGkgaW4gcmFuZ2UoMTEwKV0KYXJyPVswIGZvciBpIGluIHJhbmdlKDExMCldCndoaWxlKHQ+MCk6CiAgICB2LG49bWFwKGludCxyYXdfaW5wdXQoKS5zcGxpdCgpKSAKICAgIHBbMF0scFsxXSxhMCxiMCxjMCxtMD1tYXAoaW50LHJhd19pbnB1dCgpLnNwbGl0KCkpCiAgICBxWzBdLHFbMV0sYTEsYjEsYzEsbTE9bWFwKGludCxyYXdfaW5wdXQoKS5zcGxpdCgpKQogICAgYXJyWzBdPXBbMF0qbTErcVswXQogICAgYXJyWzFdPXBbMV0qbTErcVsxXQogICAgZm9yIGkgaW4gcmFuZ2UoMixuKToKICAgICAgICBwW2ldPShhMCphMCpwW2ktMV0rYjAqcFtpLTJdK2MwKSVtMAogICAgICAgIHFbaV09KGExKmExKnFbaS0xXStiMSpxW2ktMl0rYzEpJW0xCiAgICAgICAgYXJyW2ldPShwW2ldKm0xK3FbaV0pCiAgICB0ZW1wPTEKICAgIGZvciBpIGluIHJhbmdlKDAsbik6CiAgICAgICAgdGVtcCo9YXJyW2ldCiAgICAgICAgdGVtcCU9KE1PRC0xKQogICAgICAgIGlmKHRlbXA9PTApOgogICAgICAgICAgICBicmVhazsKICAgIGlmKHYlTU9EPT0wKWFuZCh0ZW1wIT0wKToKICAgICAgICBwcmludCgwKQogICAgZWxpZih0ZW1wPT0wKToKICAgICAgICBwcmludCgxKQogICAgZWxzZToKICAgICAgICBwcmludCAocG93ZXIodix0ZW1wKSkKICAgIHQtPTEg

MwoxIDIKMSAxIDEgMSAxIDEKMSAxIDEgMSAxIDEKMyAyCjEgMSAxIDEgMSAyCjIgMSAxIDEgMSAxCjMgMwoxIDEgMSAxIDEgMgoxIDEgMCAwIDAgMg==

3
1 2
1 1 1 1 1 1
1 1 1 1 1 1
3 2
1 1 1 1 1 2
2 1 1 1 1 1
3 3
1 1 1 1 1 2
1 1 0 0 0 2