p02858 DISCO Presents Discovery Channel Code Contest 2020 Qual - DISCOSMOS_9764
In 2937, DISCO creates a new universe called DISCOSMOS to celebrate its 1000-th anniversary.

DISCOSMOS can be described as an H \times W grid. Let (i, j) (1 \leq i \leq H, 1 \leq j \leq W) denote the square at the i-th row from the top and the j-th column from the left.

At time 0, one robot will be placed onto each square. Each robot is one of the following three types:

* Type-H: Does not move at all.
* Type-R: If a robot of this type is in (i, j) at time t, it will be in (i, j+1) at time t+1. If it is in (i, W) at time t, however, it will be instead in (i, 1) at time t+1. (The robots do not collide with each other.)
* Type-D: If a robot of this type is in (i, j) at time t, it will be in (i+1, j) at time t+1. If it is in (H, j) at time t, however, it will be instead in (1, j) at time t+1.



There are 3^{H \times W} possible ways to place these robots. In how many of them will every square be occupied by one robot at times 0, T, 2T, 3T, 4T, and all subsequent multiples of T?

Since the count can be enormous, compute it modulo (10^9 + 7).

Constraints

* 1 \leq H \leq 10^9
* 1 \leq W \leq 10^9
* 1 \leq T \leq 10^9
* H, W, T are all integers.

Input

Input is given from Standard Input in the following format:


H W T


Output

Print the number of ways to place the robots that satisfy the condition, modulo (10^9 + 7).

Examples

Input

2 2 1


Output

9


Input

869 120 1001


Output

672919729
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (1000000007U)
struct Modint{
  unsigned val;
  Modint(){
    val=0;
  }
  Modint(int a){
    val = ord(a);
  }
  Modint(unsigned a){
    val = ord(a);
  }
  Modint(long long a){
    val = ord(a);
  }
  Modint(unsigned long long a){
    val = ord(a);
  }
  inline unsigned ord(unsigned a){
    return a%MD;
  }
  inline unsigned ord(int a){
    a %= MD;
    if(a < 0){
      a += MD;
    }
    return a;
  }
  inline unsigned ord(unsigned long long a){
    return a%MD;
  }
  inline unsigned ord(long long a){
    a %= MD;
    if(a < 0){
      a += MD;
    }
    return a;
  }
  inline unsigned get(){
    return val;
  }
  inline Modint &operator+=(Modint a){
    val += a.val;
    if(val >= MD){
      val -= MD;
    }
    return *this;
  }
  inline Modint &operator-=(Modint a){
    if(val < a.val){
      val = val + MD - a.val;
    }
    else{
      val -= a.val;
    }
    return *this;
  }
  inline Modint &operator*=(Modint a){
    val = ((unsigned long long)val*a.val)%MD;
    return *this;
  }
  inline Modint &operator/=(Modint a){
    return *this *= a.inverse();
  }
  inline Modint operator+(Modint a){
    return Modint(*this)+=a;
  }
  inline Modint operator-(Modint a){
    return Modint(*this)-=a;
  }
  inline Modint operator*(Modint a){
    return Modint(*this)*=a;
  }
  inline Modint operator/(Modint a){
    return Modint(*this)/=a;
  }
  inline Modint operator+(int a){
    return Modint(*this)+=Modint(a);
  }
  inline Modint operator-(int a){
    return Modint(*this)-=Modint(a);
  }
  inline Modint operator*(int a){
    return Modint(*this)*=Modint(a);
  }
  inline Modint operator/(int a){
    return Modint(*this)/=Modint(a);
  }
  inline Modint operator+(long long a){
    return Modint(*this)+=Modint(a);
  }
  inline Modint operator-(long long a){
    return Modint(*this)-=Modint(a);
  }
  inline Modint operator*(long long a){
    return Modint(*this)*=Modint(a);
  }
  inline Modint operator/(long long a){
    return Modint(*this)/=Modint(a);
  }
  inline Modint operator-(void){
    Modint res;
    if(val){
      res.val=MD-val;
    }
    else{
      res.val=0;
    }
    return res;
  }
  inline operator bool(void){
    return val!=0;
  }
  inline operator int(void){
    return get();
  }
  inline operator long long(void){
    return get();
  }
  inline Modint inverse(){
    int a = val;
    int b = MD;
    int u = 1;
    int v = 0;
    int t;
    Modint res;
    while(b){
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if(u < 0){
      u += MD;
    }
    res.val = u;
    return res;
  }
  inline Modint pw(unsigned long long b){
    Modint a(*this);
    Modint res;
    res.val = 1;
    while(b){
      if(b&1){
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  inline bool operator==(int a){
    return ord(a)==val;
  }
  inline bool operator!=(int a){
    return ord(a)!=val;
  }
}
;
inline Modint operator+(int a, Modint b){
  return Modint(a)+=b;
}
inline Modint operator-(int a, Modint b){
  return Modint(a)-=b;
}
inline Modint operator*(int a, Modint b){
  return Modint(a)*=b;
}
inline Modint operator/(int a, Modint b){
  return Modint(a)/=b;
}
inline Modint operator+(long long a, Modint b){
  return Modint(a)+=b;
}
inline Modint operator-(long long a, Modint b){
  return Modint(a)-=b;
}
inline Modint operator*(long long a, Modint b){
  return Modint(a)*=b;
}
inline Modint operator/(long long a, Modint b){
  return Modint(a)/=b;
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(Modint x){
  int i;
  i = (int)x;
  wt_L(i);
}
template<class T, class S> inline T pow_L(T a, S b){
  T res = 1;
  res = 1;
  while(b){
    if(b&1){
      res *= a;
    }
    b >>= 1;
    a *= a;
  }
  return res;
}
inline double pow_L(double a, double b){
  return pow(a,b);
}
template<class T> inline T GCD_L(T a,T b){
  T r;
  while(a){
    r=b;
    b=a;
    a=r%a;
  }
  return b;
}
int H;
int W;
int T;
int main(){
  int g1;
  int g2;
  int g;
  Modint res = 1;
  rd(H);
  rd(W);
  rd(T);
  g1 =GCD_L(H, T);
  H /= g1;
  g2 =GCD_L(W, T);
  W /= g2;
  g =GCD_L(H, W);
  res += (pow_L(Modint(2),g)) - 2;
  res += (pow_L(Modint(2),H)) - 1;
  res += (pow_L(Modint(2),W)) - 1;
  (res = pow_L(res,g1));
  (res = pow_L(res,g2));
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20191123-1

// --- original code ---
// int H, W, T;
// 
// {
//   int g1, g2, g;
//   Modint res = 1;
//   rd(H,W,T);
// 
//   g1 = gcd(H,T);
//   H /= g1;
//   g2 = gcd(W,T);
//   W /= g2;
// 
//   g = gcd(H,W);
//   res += (Modint(2) ** g) - 2;
//   res += (Modint(2) ** H) - 1;
//   res += (Modint(2) ** W) - 1;
// 
//   res **= g1;
//   res **= g2;
//   wt(res);
// }

869 120 1001 2 2 1 869 80 1001 328 80 1001 328 102 1011 328 102 1111 279 102 1111 25 102 1111 25 122 1111 25 63 1111 25 89 1111 1486 120 1001 869 80 1101 328 117 1011 40 102 1111 328 60 1111 117 102 1111 24 102 1111 9 122 1111 24 63 1111 11 89 1111 141 120 1001 869 47 1101 328 234 1011 40 29 1111 328 60 1110 117 102 1110 27 102 1111 8 122 1111 24 63 1011 11 128 1111 141 53 1001 869 47 1111 171 80 0101 328 81 1011 544 60 1111 117 102 0111 27 102 1011 8 153 1111 24 57 1011 11 48 1111 869 94 1111 171 80 0111 118 81 1011 23 29 1101 544 60 1101 117 102 0110 27 108 1011 10 153 1111 24 57 1111 11 48 1110 168 53 0001 693 94 1111 171 53 0111 213 81 1011 22 29 1101 544 89 1111 117 66 0111 44 108 1011 13 153 1111 13 48 1110 168 103 0001 675 94 1111 171 53 0011 213 133 1011 25 29 1101 1087 89 1111 229 66 0111 44 108 1111 13 153 1101 27 57 1101 7 48 1110 168 172 0001 254 94 1111 213 210 1011 3 29 1101 1087 86 1111 229 42 0111 22 108 1111 13 153 1001 27 57 0101 5 48 1110 251 172 0001 254 7 1111 299 53 0001 34 210 1011 3 22 1101 411 42 0111 22 108 1101 13 228 1001 5 70 1110 254 6 1111 299 45 0001 34 210 0011 3 35 1101 400 42 0111 32 108 1101 8 228 1001 22 57 0111 5 115 1110 251 7 0101 11 6 1111
672919729 9 540377089
 238803603
 261361566
 647647330
 58769
 939039550
 991048692
 324726435
 313816333
 960152848
 238641419
 407646568
 417105196
 278558727
 841656819
 922262396
 957494772
 307949225
 136354903
 236970719
 229370448
 946276091
 48490987
 262704069
 144035005
 39702845
 957494518
 307634569
 593254994
 939287752
 423340508
 630725753
 735307340
 384027742
 485235061
 631919805
 157921605
 271782599
 10290134
 432672202
 519311816
 400679409
 545259519
 522092841
 270604399
 919957460
 157922373
 83826784
 723205254
 958451180
 735186242
 412313252
 460034215
 541065215
 127893126
 194387215
 681550791
 157929541
 297983448
 577730805
 378780126
 325775212
 694221187
 570425343
 496505363
 289454849
 282417197
 784047163
 218865228
 404785941
 34929816
 666592122
 698379166
 582975580
 1276197
 123242493
 753289343
 664476711
 201267296
 220543434
 355445642
 698211447
 852715981
 740821471
 899722747
 982361002
 449054296
 191072948
 284885353
 698211385
 32867919
 611619217
 133144039
 468707491
 541641121
 710791753
 562367039
 880021930
 87276542
 533072736
