Toric necklaces P26979


Statement
 

pdf   zip

html

A shop wants to commercialize a new kind of jewellery: toric necklaces! Given an infinite supply of k different beads, a toric necklace is built by picking n · m beads and placing them on an n× m grid. Then we join every pair of beads that are vertically adjacent with blue thread, and every pair of beads that are horizontally adjacent with red thread. Finally, we use blue thread to join the j-th bead of the first row with the j-th bead of the last row, and red thread to join the i-th bead of the first column with the i-th bead of the last column.

Here, we consider two toric necklaces equivalent if one can be obtained from the other by horizontal and/or vertical rotations. In other words, two necklaces defined by the matrices A[0… n−1,0… m−1] and B[0… n−1,0… m−1] are equivalent if there exist x and y such that A[i,j] = B[(i+x) modn, (j+y) modm] for every i and j.

Given n, m and k, can you compute the number of different toric necklaces?

Input

Input consists of several different cases, each one with n, m and k, all between 1 and 106.

Output

For every case, print the number of n× m toric necklaces that can be built with beads of k different kinds, modulo 109 + 7.

Public test cases
  • Input

    1 2 2
    1 2 3
    2 2 2
    2 3 3
    3 5 1
    4 6 2
    1 1 500
    10 20 30
    720680 33199 792347
    1000000 1000000 1000000
    

    Output

    3
    6
    7
    130
    1
    699600
    500
    798528669
    229776682
    320081768
    
  • Information
    Author
    Lander Ramos
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tretzè Concurs de Programació de la UPC - Semifinal
    Date
    2015-07-01