SPACESET - Space settlement

A long time ago in a galaxy far far away ... The empire has built a grand new space colony. This colony has m levels and each level consists of n settlements. Space settlements are connected by routes along which spacecrafts fly.

A level is a ring shaped construction with the n space settlements lying on it. The ring provides routes for the spacecrafts. Within a level, travelling is only possible along the ring. The ring shaped route will be present irrespective of the number of settlements in the level.

Levels are organised in a heirarchy. Excellent connectivity is provided between levels. Each settlement in a level is connected by a route to every settlement in the levels immediately above and below it. The topmost and the bottom-most levels are also connected in a similar fashion.

Our adventurous space pilot -- Han Solo wants to ferry people between space settlements. Solo's spacecraft can navigate a path having exactly k stops, no more no less.

Given the values of k, n and m you have to find the number of paths in the space colony that he can use for his work.

Notes:

    1. A settlement can be visited any number of times in a journey.

    2. A path is considered as a sequence of vertices such that there is an edge between consecutive vertices. Two path's are considered to be different if they differ in any one vertex.

    3. The topmost and bottom-most levels are connected only if they are different.

    4. Image for clarification

    Here the black dots represent the settlements. The connections are showm as rings and lines.

Input

First line of input contains T, the number of test cases. Every test case will contain the values of m, n and k.

Output

Output contains T lines, one for each test case. Every line will consist of the total number of routes possible mod 12345678.

Example

Input:
5
1 1 1
1 2 1
3 3 56
4 3 4
691 60 97764

Output:
1
2
8019378
6144
470730 

Constraints

Dataset 1: T ≤ 100, m ≤ 1000, n ≤ 1000, k ≤ 100000 Time limit: 5s

Dataset 2: T ≤ 100, m ≤ 10^8, n ≤ 10^8, k ≤ 10^8 Time limit: 5s


Được gửi lên bởi:Race with time
Ngày:2009-02-19
Thời gian chạy:4.489s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Code Craft 09

hide comments
2013-07-31 09:48:14 a;slkfjasl;fkj
Đọc đề khó hiểu ghê :(
2011-07-17 21:02:59 pitago
Đề bài đúng ! Cần đọc kỹ để hiểu rõ đề !!!
2011-07-17 13:38:58 Kimo


Last edit: 2011-08-13 14:59:27
2010-09-21 16:47:49 nameless
Mấy cái test bẫy đúng là khó thật :(
2009-04-11 12:44:01 __PuppY__
phải là m*n*(2*n+2)^(k-1)%modul mới đúng chứ
mà muốn accept cũng khổ, mấy cái test bẫy ...:(

Last edit: 2009-04-11 13:03:59
2009-04-10 14:29:42 RR
Cong thuc dung ma. Nhung anh post cong thuc len the thi cac users khac accept de dang qua +_+
2009-04-10 13:21:55 Thiêm Nguyễn
Nói liều vừa thôi chứ. Anh AC gần như là đầu tiên bài này ( sau RR)
2009-04-10 09:19:09 __PuppY__
Công thức sai toét kìa anh Thiêm ơi
2009-04-07 13:49:14 Thiêm Nguyễn
1. Combinatorics type.
2. Formula: m*(2*n+2)^(k-1)%modul except some special cases. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.