拉尔夫有一个魔法场,分为 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 放入每个块中。