#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
long long n,x,y;
long long pw(long long a,long long b,long long mod) {
long long ans=1;
a%=mod;
while (b){
if (b&1){
ans=ansa%mod;
}
a=aa%mod;
b>>=1;
}
return ans;
}
long long f(long long n, long long x, long long y){
return ((pw(x+y,n,MOD)pw(2,n,MOD))%MOD+pw(2,n-1,MOD))%MOD;
}
struct Mat{
long long mat[2][2];
Mat(){
mat[0][0]=mat[1][1]=1;
mat[0][1]=mat[1][0]=0;
}
Mat operator(const Mat& ot) const{
Mat res;
res.mat[0][0]=(mat[0][0]*ot.mat[0][0]+mat[0][1]*ot.mat[1][0])%MOD;
res.mat[0][1]=(mat[0][0]*ot.mat[0][1]+mat[0][1]ot.mat[1][1])%MOD;
res.mat[1][0]=(mat[1][0]ot.mat[0][0]+mat[1][1]ot.mat[1][0])%MOD;
res.mat[1][1]=(mat[1][0]ot.mat[0][1]+mat[1][1]ot.mat[1][1])%MOD;
return res;
}
};
Mat mat_pw(Mat a,long long b){
Mat res;
while (b) {
if (b&1){
res=resa;
}
a=aa;
b>>=1;
}
return res;
}
long long fib(long long n){
if (n==0){
return 0;
}
Mat base;
base.mat[0][0]=f(x,n,x+y);
base.mat[0][1]=f(y,x+y,n);
base.mat[1][0]=1;
base.mat[1][1]=0;
Mat res=mat_pw(base,n-1);
return res.mat[0][0];
}
long long g(long long i,long long x,long long y) {
if (i<=1){
long long fi=f(i,x,y);
long long fx=f(x,i,y-1);
long long pff=pw(fi,fx,MOD);
return pff;
}
return fib(i);
}
vector<int> p;
bool vis[1000010];
void init(){
memset(vis,1,sizeof vis);
vis[0]=vis[1]=0;
for (int i=2;i<1000010;i++) {
if (vis[i]){
p.push_back(i);
for (int j=2i;j<1000010;j+=i) {
vis[j]=0;
}
}
}
}
long long cd(long long x){
long long ans=1;
for (int ps:p){
long long et=0;
long long pr=ps;
while (pr<=x){
et+=x/pr;
if (pr>x/ps){
break;
}
pr=ps;
}
ans=(ans(et+1))%MOD;
}
return ans;
}
int main() {
init();
cin>>n>>x>>y;
long long gnxy=__gcd(n,x+y);
long long gg=g(gnxy,x,y);
long long gm=gg%(100000);
long long phi=cd(gm);
cout<<phi<<endl;
return 0;
}
