SPACESET - Space settlement

Đã lâu lắm rồi, ở một thiên hà xa xôi ... Một đế chế đã xây dựng nên một trạm không gian vĩ đại. Trạm không gian này có m tầng, và mỗi tầng gồm có n khu vực. Các khu vực được nối với nhau bởi các tuyến đường để các tàu không gian có thể bay qua.

Một tầng là một vòng tròn với n khu vực được đặt trên đó. Vòng tròn cung cấp các tuyến đường bay cho các tàu không gian. Trong vòng một tầng, việc di chuyển chỉ được thực hiện dọc theo vòng tròn đó. Vòng tròn định hướng đường bay sẽ luôn tồn tại, bất chấp số lượng khu vực ở trong tầng đó.

Các tầng được tổ chức thành một hệ thống. Một sự kết nối hoàn hảo được cung cấp giữa các tầng. Tại mỗi khu vực trong một tầng sẽ có các tuyến đường nối tới mọi khu vực ở tầng ngay trên và ngay dưới nó. Tầng trên cùng và dưới cùng cũng được nối theo cách tương tự.

Chàng phi hành gia thích phiêu lưu -- Han Solo muốn chở mọi người giữa các khu vực. Tàu không gian của Solo có thể bay theo một hành trình có chính xác k điểm dừng, không hơn không kém.

Cho giá trị của k, n và m. Bạn phải tính số hành trình trong trạm không gian mà Solo có thể dùng để thực hiện công việc của mình.

Lưu ý

    1. Một khu vực có thể được thăm bao nhiêu lần tùy ý trong 1 hành trình.

    2. Một hành trình được coi là một dãy các đỉnh sao cho tồn tại một cạnh giữa 2 đỉnh liên tiếp. Hai hành trình được coi là khác nhau nếu chúng khác nhau tại một đỉnh bất kỳ.

    3. Tầng trên cùng và dưới cùng chỉ được nối với nhau nếu như chúng khác nhau.

    4. Hình ảnh tượng trưng

    Trong hình, các dấu chấm màu đen thể hiện các khu vực. Sự kết nối được biểu diễn bằng các vòng tròn và đường thẳng.

Input

Dòng đầu chứa T, số lượng test. Mỗi test chứa các giá trị của m, n và k.

Output

Chứa T dòng, mỗi dòng cho 1 test. Mỗi dòng sẽ ghi phần dư của tổng số hành trình có thể sử dụng khi chia cho 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.