Migrated from Lutece 2275 快去睡觉

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

qhqh正在统计宿舍集训人数以方便安排住宿。众所周知，秦皇家里有一座岛。秦皇得知此事后立马安排人在清水河修了栋楼, "我的阿房宫还蛮大的，你们随便住"。

qhqh不知道具体会是哪些人参加暑期集训，秦皇的阿房宫大概还要修个十年所以qhqh也不知道到底有多大。假设最终会有$k$人参加暑期集训，秦皇的楼有$n$层高，每一层有$m$个房间，每间房间可以住无限人。qhqh想知道把k个无法区分/可区分的人安排进无法区分/可区分的房间后每个房间都有人住的方案数有多少。

qhqh去睡觉了，希望你能够在他睡醒之前解决这个问题。

Input

多组数据。

每组一行三个数n, m, k。

Output

每组一行四个数，分别代表在人和房间可区分,人无法区分房间可区分,人可区分房间无法区分,人和房间无法区分的情况下在模1e9 + 7意义下的方案数。

Samples

2 2 4

24 1 1 1

2 2 9

186480 56 7770 6

Constraints

$数据组数\leq100,000$

$1\leq{n, m, k}\leq1,000$

Resources

2019 UESTC ACM Training for math and geometry