Codeforces 894B

题目链接：https://cn.vjudge.net/problem/CodeForces-894B

Ralph has a magic field which is divided into n × m blocks. That is to say, there are n rows and m columns on the field. Ralph can put an integer in each block. However, the magic field doesn't always work properly. It works only if the product of integers in each row and each column equals to k, where k is either 1 or -1.

Now Ralph wants you to figure out the number of ways to put numbers in each block in such a way that the magic field works properly. Two ways are considered different if and only if there exists at least one block where the numbers in the first way and in the second way are different. You are asked to output the answer modulo 1000000007 = 10⁹ + 7.

Note that there is no range of the numbers to put in the blocks, but we can prove that the answer is not infinity.

Input

The only line contains three integers n, m and k (1 ≤ n, m ≤ 10¹⁸, k is either 1 or -1).

Output

Print a single number denoting the answer modulo 1000000007.

Example

Input

1 1 -1

Output

Input

1 3 1

Output

Input

3 3 -1

Output

Note

In the first example the only way is to put -1 into the only block.

In the second example the only way is to put 1 into every block.

题意：

给出一个n*m的方格矩阵，给定k=-1或1，在所有方格里面填上-1或1，使得每行每列的乘积都为k，则算作一种方案，求总共有多少种不同方案。

题解：

①当n+m为奇数，k=-1时，方案数=0；

　因为这时，n和m必然为一奇一偶，不妨设n为奇数，m为偶数；

　则在每一行上必然要放奇数个-1，那么这样可以知道-1的总个数是偶数（奇数行，每行奇数个-1）；

　但是，同时每一列上也要放奇数个-1，那么-1的总个数是奇数（偶数列，每列奇数个-1）；

　互相矛盾，所以不存在这样的方案。

②其他情况下，存在至少一种方案，此时我们设有矩阵A[n][m]：

　　a[1][1]　……………………　a[1][m-1]　a[1][m]

　　……………………………………………………

　　a[n-1][1]　……………… a[n-1][m-1] a[n-1][m]

　　a[n][1]　……………………　a[n][m-1]　a[n][m]

　此时矩阵A[n-1][m-1]里面可以随意填入1或者-1，则对应的 a[n][1] ~ a[n-1][m] 和 a[1][m] ~ a[n-1][m] 需要取-1或者1来使得行列为k；

　例如：，因为，所以和，所以a[n][m]存在，所以方案存在。

　因此我们不能难算出方案数为；

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll n,m;int k;
ll fpow(ll a,ll b){//快速幂
    ll r=1,base=a%MOD;
    while(b){
        if(b&1) r*=base , r%=MOD;
        base*=base;
        base%=MOD;
        b>>=1;
    }
    return r;
}
int main()
{
    cin>>n>>m>>k;
    if(k==-1 && (n+m)%2==1)
    {
        printf("0
");
        return 0;
    }

    ll ans=fpow(2,n-1);
    ans=fpow(ans,m-1);
    cout<<ans<<endl;
}

PS.显然最大10^18数量级的n和m直接乘起来肯定爆炸longlong，所以分两次快速幂即可。

PS2.此处#include<bits/stdc++.h>的话，因为包含进了pow()函数，这样我们就要给快速幂函数改个名字（比如fpow……），避免错误。