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.

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