Informatica Online Judge

  행렬 만들기 [2126 / 084E]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 11   Total Tried : 12


The Champion of this Problem (C++) : gs16109 - 0ms / 529byte
My Best Submission (C++) : N/A

[Codeforces modify]

Background

경곽이는 다음 조건을 만족하는 행렬을 만들고자 한다.

==============================================================================================

- 행렬은 $n$행 $m$열로 이루어져 있다.

- $k$값이 주어지는데, 임의의 $i$행 $j$열의 값을 채울 때 $i$행의 모든 원소들의 곱이 반드시 $k$가 되고, $j$열의 모든 원소들의 곱이 반드시 $k$가 되도록 모든 $i$행 $j$열의 값을 채워야 한다.

- $k$의 값은 $1$ 또는 $-1$이다.

==============================================================================================

경곽이는 $n$, $m$, $k$가 주어질 때, 위와 같은 조건을 만족하는 행렬을 몇 개나 만들 수 있는지 궁금해졌으나 코딩을 할 줄 몰라서 여러분의 도움을 필요로 한다.

프로그램을 만들어서 경곽이를 도와주자.

Input

첫 번째 줄에 $n$, $m$, $k$가 공백으로 구분되어 입력된다.

[입력값의 정의역]

$1≤n,m≤10^{18}$
$k∈\{-1, 1\}$

Output

경우의 수가 너무 많으니 전체 답을 $10^9+7$로 나눈 나머지를 출력한다.

IO Example

입력1
1 1 -1

출력1
1

* 설명 :
1행 1열로 모든 행의 곱과 열의 곱이 -1이 되도록 채우려면 1행 1열에 -1을 배치하는 방법 뿐이다.

입력2
1 3 1

출력2
1

* 설명 :
1행 3열로 구성되어 있으면서 모든 행과 열의 곱이 1이 되도록 값을 배치하는 방법은 모든 원소를 1로 만드는 방법 뿐이다. 따라서 1가지

입력3
3 3 -1

출력3
16

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]