F. 试题F：等差等比有联系 公差公比求通项 15’

描述

已知一个等比数列的某三项分别是a,b,c, 且已知第一项是a，求等比数列的第N项最大是多少。

输入

输入共一行，输出4个整数a,b,c,N。

输出

输出第N项，结果对10^9取模

样例

输入

2 8 32 10

输出

524288

输入

3 9 81 5

输出

243

提示

数据范围

对于20%的数据，1<=a<=b<=c<=150, n<=10

对于80%的数据，n<=10^6

对于100%的数据，n<=10^{18},1<=a<=b<=c<=10^9

 

 

 

 

 

def sieve(x,i):
    while x%i==0:
        x//=i;
    return x==1;
def main():
    a,b,c,n=map(int,input().split());
    x,y=b//a,c//a;
    q=1;
    for i in range(min(x,y),1,-1):
        if sieve(x,i) and sieve(y,i):
            q=i;
            break;
    print(a*pow(q,n-1,int(1e9))%int(1e9));##自带 快速幂
main();