POJ.2115 C Looooops

1.Problem
http://poj.org/problem?id=2115

2.Idea
ext gcd

3.Source

 Int a, b, c, k;  
 Int m;  
 // a x + b y = gcd(a, b)  
 Int extgcd(Int a, Int b, Int &x, Int &y) {  
      Int g = a; x = 1; y = 0;  
      if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;  
      return g;  
 }  
 void solve()  
 {  
      while (scanf("%lld%lld%lld%lld", &a, &b, &c, &k) > 0) {  
           if (a == 0 && b == 0 && c == 0 && k == 0) {  
                break;  
           }  
           Int m = (Int)1 << k, x, y;  
           Int g = extgcd(c, m, x, y);  
           if ((b - a) % g) {  
                printf("FOREVER\n");  
           }  
           else {  
                x = (x*((b - a) / g) % (m / g) + (m / g)) % (m / g);  
                printf("%lld\n", x);  
           }  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }