← 返回题目列表

Codeforces · 894/B

B. 拉尔夫和他的魔法场

中文机器翻译题面 查看原题

拉尔夫有一个魔法场,分为 n × m 块。也就是说,场地上有n行m列。拉尔夫可以在每个块中放入一个整数。然而,魔法场并不总是能正常工作。仅当每行和每列中的整数的乘积等于 k ​​时才有效,其中 k 为 1 或 -1。

现在拉尔夫希望你找出在每个块中放置数字的方法的数量,以便魔法场正常工作。当且仅当存在至少一个块,其中第一种方式和第二种方式中的数字不同时,两种方式被认为是不同的。系统要求您输出模 1000000007 = 109 + 7 的答案。

请注意,放入块中的数字没有范围,但我们可以证明答案不是无穷大。

输入

唯一一行包含三个整数 n、m 和 k(1 ≤ n,m ≤ 1018,k 为 1 或 -1)。

输出

打印一个数字,表示答案模 1000000007。

示例

输入 #1

1 1 -1

输出 #1

1

输入 #2

1 3 1

输出 #2

1

输入 #3

3 3 -1

输出 #3

16

注意

在第一个示例中,唯一的方法是将 -1 放入唯一的块中。

在第二个示例中,唯一的方法是将 1 放入每个块中。