Buildings

세계화된 세상에서 떠돌이 상인으로 살아온 Alan은 늘 이사를 다녔다. 같은 마을에서 몇 년 이상 살아본 적이 거의 없었고, 마음이 다른 곳을 그리면 곧 새 마을로 옮겼다. 하지만 이번 마을은 지금까지 중 가장 마음에 든다. 그저 색이 다채롭기 때문이다. Alan은 최근 멋진 산들 사이에 자리한 작은 도시 Colorville로 이사했다. 이곳에서 Alan은 마침내 정착해 자신만의 집, 그러니까 자랑할 만한 큰 집을 짓기로 했다.

Colorville에서는 많은 사람이 각자 집을 가지고 있고, 집마다 서로 다른 색 패턴으로 칠해져 있어서 두 집이 똑같이 보이는 일은 없다. 벽은 정확히 n × n개의 정사각형으로 이루어져 있고, 각 정사각형은 주어진 색으로 칠해진다. 창문과 문도 고유한 "색"으로 본다. 집의 벽들은 정m각형 모양으로 배치되고, 그 위에 지붕이 올라간다. Colorville의 오랜 전통에 따르면 지붕은 Colorville 주민의 일체감을 드러내야 하므로, Colorville의 모든 지붕은 같은 색이다.

그림 B.1: n = 3, m = 6일 때의 집 설계 예시.

물론 Alan은 이 관습을 따라야 주변에 잘 어울릴 수 있다는 것을 안다. 그런데 고를 수 있는 설계가 너무 많다. Alan에게 가능한 집 설계가 몇 가지인지 알려줄 수 있는가? (회전만으로 서로 옮겨갈 수 있는 두 설계는 당연히 같은 것이다.)

입력은 다음과 같다.

• 세 정수 n, m, c가 있는 한 줄. 여기서

  • n (1 ≤ n ≤ 500)은 모든 벽의 한 변의 길이, 즉 모든 벽이 n × n개의 정사각형으로 이루어져 있음을 뜻한다.
  • m (3 ≤ m ≤ 500)은 정다각형의 꼭짓점 개수이다.
  • c (1 ≤ c ≤ 500)는 서로 다른 색의 개수이다.

가능한 서로 다른 집 설계의 수 s를 출력한다. s는 매우 클 수 있으므로 s mod (109 + 7)을 출력한다.