#include <bits/stdc++.h>

using namespace std;
 int m=1000000007;

long countArray(int n, int k, int x) {
    n-=2;
    k--;
    
    {
       int a=1,an=1,b=1,bn=k;
       for (int i = 0; i <= n; i+=2)
       {
           a=(((long long )a+(long long )an))%m;
           an=((long long )an*(long long)k)%m;
           an=((long long )an*(long long)k)%m;
       }
       for (int i = 1; i <=n; i+=2)
       {
            b=(((long long )b+(long long )bn))%m;
           bn=((long long )bn*(long long)k)%m;
           bn=((long long )bn*(long long)k)%m;
       }
      
       if(n%2==0)
       {
         int ans=(a-b)%m;
         if(ans<0)  ans=(ans+m);
         if(x==1)
         {
            ans=(ans-1)%m;
         }
         return ans;
       }
       else
       {
          int ans=(b-a)%m;
         if(ans<0)  ans=(ans+m);
         if(x==1)
         {
           ans=(ans+1)%m;
         }
         return ans;
       }
     

    }

}

int main() {
    int n;
    int k;
    int x;
    cin >> n >> k >> x;
    long answer = countArray(n, k, x);
    cout << answer << endl;
    return 0;
}