#20 「 最大公约数 」

统计

“我国是一个有着13亿多人口、56个民族的大国,确立反映全国各族人民共同认同的价值观‘最大公约数’,使全体人民同心同德、团结奋进,关乎国家前途命运,关乎人民幸福安康。”

十九同学在电视中听到习大大讲这番话的时候,突然想到一个问题,如何求$gcd(a^b,c^d)$?,他当然知道啦,不过他想考考你。

这个数字非常大所以你只用输出它除以$10^9+7$的余数。

输入格式

输入仅一行,四个正整数,表示a,b,c,d。

输出格式

输出只有一个整数,表示答案。

样例数据

input

2 3 4 1

output

4

数据规模与约定

$1 \le a,b,c,d \le 10^9$。

时间限制:1s

空间限制:512MB

Author: Nineteen