Let's define a good tree: It is a tree with k * n nodes labeled from 0 to k * n - 1 Node…
- User
Let's define a good tree:
It is a tree with k * n nodes labeled from 0 to k * n - 1 Node i and node j are not adjacent, for all 0 <= i, j < k * n such that i div k = j div k (here div means integer division. E.g. 7 div 2 = 3)
Given n and k, how many different good trees are there? Input Two integers n(1 <= n <= 10^5), k(1<= k <=3)
Output Output the number of different good trees. As the result may be very large, just output the remainder when divided by (10^9 + 7).
Example
Input 1: 2 2
Output 1: 4
Input 2: 1 2
Output 2: 0
Input 3: 4 1
Output 3: 16
Assistant
We are asked: "Let's define a good tree: It is a tree with k * n nodes labeled from 0 to k * n - 1. Node i and node j are not adjacent, for all 0 <= i, j < k * n such that i div k = j div k (here div means integer division. E.g. 7 div 2 = 3). Given n and k, how many different good trees are there?"
Interpretation: We have labeled nodes 0,1,..., kn-1. There is a constraint that for any two nodes whose integer division by k yields the same quotient (i.e., they belong to the same block of size k: indices from kq to kq + k-1), those two nodes cannot be adjacent in the tree. So the tree must avoid edges within each group of k nodes. So we have a complete graph on kn nodes minus the edges that connect nodes in the same block (i.e., each block of size k is an independent set, no internal edges allowed). Then we want the number of spanning trees on this graph that are trees (i.e., connected acyclic subgraphs covering all vertices). Equivalent: Count the number of labeled trees on kn vertices such that no two vertices from the same block are adjacent. The tree is labeled, so distinct trees are counted as different if edge sets differ. Since it's a tree on labeled vertices, the count is some number.
Given constraints n up to 1e5, k up to 3. So we need a formula possibly. For k=1: Then each block has size 1, so the condition "Node i and node j are not adjacent, for all 0 <= i,j < kn such that i div k = j div k" if k=1, then i div 1 = i, j div 1 = j, so condition only applies when i=j? Actually "i div k = j div k" when k=1 means i = j? Because i div 1 = i, j div 1 = j, so equality means i=j. But the condition says node i and node j are not adjacent for all i,j with same quotient. Usually i and j can be the same? Usually adjacency is defined between distinct nodes. Typically tree edges connect distinct nodes. So condition likely applies for i != j with same quotient. But if k=1, there is only one node per group, so there is no pair of distinct nodes with same quotient. So the constraint is vacuously true. So good trees are all trees on n nodes (since kn = n). Number of labeled trees on n nodes is n^{n-2} (Cayley's formula). But sample: Input 4 1 output 16. For n=4, k=1 => 4 nodes, labeled 0..3. Number of labeled trees on 4 nodes is 4^{2}=16. Yes matches. So for k=1, answer is n^{n-2} (mod MOD).
For k=2,3, need formula. The constraint: Nodes are partitioned into n groups each of size k. No edges allowed within a group. So the tree must be a bipartite? Actually it's a complete k-partite graph with n parts each of size k? Wait the partition is into n groups of k nodes each. The forbidden edges are only those within each group, but edges between any two nodes from different groups are allowed. So the graph is the complete n-partite graph with each part of size k. Denote G = K_{k,k,...,k} (n times). Number of vertices = kn. We need number of spanning trees of this complete multipartite graph.
There is known formula: Number of spanning trees of complete multipartite graph K_{n1, n2, ..., nr} = n^{r-2} * ∏{i=1}^{r} (n - n_i)^{n_i - 1}? Actually there is a known formula due to Kirchhoff and particular case. Let's recall: For complete bipartite graph K{a,b}, number of spanning trees = a^{b-1} * b^{a-1}. For complete multipartite graph K_{n1, n2, ..., nr}, there is a formula: number of spanning trees = (∏{i=1}^{r} n_i^{?}) * (N)^{r-2} * something? Actually I recall a result: For complete r-partite graph with parts sizes n1, n2, ..., nr, the number of spanning trees is N^{r-2} ∏{i=1}^{r} (N - n_i)^{n_i - 1}, where N = total vertices. Check for r=2: N = a+b. Then formula gives N^{0} * (N - a)^{a-1} * (N - b)^{b-1} = (b)^{a-1} * (a)^{b-1}. Because N - a = b, N - b = a. So indeed a^{b-1} b^{a-1}. So correct.
For complete multipartite with all parts equal size k and number of parts n: N = kn, r = n. Then formula becomes: number of spanning trees = (kn)^{n-2} * ∏_{i=1}^{n} (kn - k)^{k-1} = (kn)^{n-2} * ( (kn - k)^{k-1} )^n = (kn)^{n-2} * (k(n-1))^{n(k-1)}? Wait (kn - k) = k(n-1). So (kn - k)^{k-1} per part, raised to the n: (k(n-1))^{n(k-1)}. So total = (kn)^{n-2} * (k(n-1))^{n(k-1)}.
But careful: The formula I recall is for number of spanning trees of complete multipartite graph. However I need to verify if it's indeed correct. There's known result: Number of spanning trees of the complete multipartite graph K_{n1,...,nr} = n^{r-2} ∏_{i=1}^{r} (n - n_i)^{n_i - 1}, where n = ∑ n_i. Yes that is a standard result (see e.g., "The number of spanning trees in a complete multipartite graph"). So yes.
Thus for k=2: N = 2n, r = n. Then number = (2n)^{n-2} * (2n - 2)^{n(2-1)= n}? Wait (k-1)=1, so exponent n(k-1)=n. And (kn - k)=2n-2 = 2(n-1). So = (2n)^{n-2} * (2(n-1))^{n}.
But sample: Input: 2 2 (n=2, k=2). Then formula gives: N = 4, (2n)^{n-2} = (4)^{0} = 1. (2(n-1))^n = (2*(1))^2 = 2^2=4. So total = 4. Sample output is 4. Good.
Input: 1 2 (n=1, k=2). Then there is only one group of size 2, but condition says nodes i and j with same quotient (i div 2 = j div 2 = 0) cannot be adjacent. Since there are two nodes, and they cannot be adjacent. A tree on 2 nodes must have exactly one edge connecting them. But that edge is forbidden because they are in same group. So no tree exists. So answer 0. Using formula: N = 2, (2n)^{n-2} = (2)^{ -1}? n-2 = -1, which is problematic. Actually the formula assumes r >= 2? Because for r=1, the graph is just an independent set? Actually complete 1-partite graph with part of size 2 is just two nodes with no edges? But complete multipartite with one part means it's a graph with no edges, because edges exist only between distinct parts. So it's not a complete graph on those vertices, but rather there are no internal edges, and since only one part, there are no inter-part edges. So the graph is empty. So no spanning tree. So the formula probably doesn't apply for n=1 (r=1). For n>=2, formula works. And indeed sample for n=1, answer is 0. So we must treat n=1 separately for k>1? For k=2 and n=1, output 0; for k=3 and n=1, similarly: 3 nodes, but cannot have edges within the group, so no edges allowed at all because all nodes are in same group. But tree on 3 nodes needs 2 edges; they'd have to connect nodes, but any edge between two nodes in the same group is forbidden, but since all three are same group, no edges allowed. So answer 0. Also for n=1, k=1, tree on 1 node: n=1, k=1 => kn=1, number of trees on 1 node is 1? Usually Cayley's formula says 1^{ -1}? But we treat n=1 separately: For k=1, n=1, output 1? But given constraints maybe n>=1, but sample 4 1 gave 16. For n=1, 1 1: would that be considered? There's no sample. But according to formula n^{n-2}, 1^{-1} is undefined; but known count: number of labeled trees on 1 vertex is 1. So we might need to handle base cases.
Thus for general n,k, answer = number of spanning trees of complete n-partite graph with each part size k, provided n>=2. For n=1, answer = 0 if k>1 else 1 if k=1.
But wait: Is the graph exactly the complete multipartite? The condition only forbids edges within each block. It does not require edges between blocks to be present? But the tree is defined on the set of nodes, but we are counting trees that satisfy the adjacency constraint. The underlying complete graph on all nodes includes edges within blocks as well, but those are disallowed. So the allowed edges are exactly all inter-block edges. So the graph is exactly the complement of intra-block edges: which is the complete n-partite graph with parts each of size k. Yes.
Thus number of good trees = number of spanning trees of K_{k,k,...,k} (n parts). So formula above holds for n>=2.
But is the formula correct for k=3? Let's test with small numbers. For n=2, k=3: total nodes =6. Graph is complete bipartite with parts size 3 each? Actually 2 parts each of size 3 => complete bipartite K_{3,3}. Number of spanning trees of K_{3,3} = 3^{3-1} * 3^{3-1} = 3^2 * 3^2 = 99=81? Wait formula for bipartite: a^{b-1} b^{a-1} = 3^{2} * 3^{2} = 99=81. Using multipartite formula with r=2: N=6, (6)^{0}=1, (N - n1)^{n1-1} (N - n2)^{n2-1} = (6-3)^{2}(6-3)^{2}=3^23^2=81. So correct.
For n=3, k=3: total nodes=9, parts =3 each size3. Number according to formula: (9)^{3-2}=9^{1}=9; (kn - k) = 9-3=6, exponent per part (k-1)=2, raised to power n=3 => 6^{6}? Actually (kn - k)^{k-1} = 6^2=36 per part, product over 3 parts = 36^3 = 46656. Multiply by 9 gives 9*46656=419904. But need to verify if this is integer. Possibly correct.
But we must ensure formula for r parts (n parts) with equal sizes k: = (kn)^{n-2} * (k(n-1))^{n(k-1)}. That's the expression. Check for n=2, k=3: (6)^{0}=1; (k(n-1)=31=3); exponent n(k-1)=22=4 => 3^4=81. Yes matches.
Now we must compute this modulo MOD=1e9+7 for n up to 1e5, k up to 3. So we need fast exponentiation. Since n can be large, we can compute (kn)^{n-2} * (k(n-1))^{n(k-1)} mod MOD. But careful: When n=1, we handle separately. Also when n=2, exponent n-2=0, so that term is 1. For n=1, the expression would have n-2 = -1, invalid. So base case.
Edge cases: k=1 gives n^{n-2} for n>=2? But our derived formula for k=1: then k(n-1)=0? Wait for k=1, k(n-1)=0, and exponent n(k-1)=0, so (0)^0? That's ambiguous. But we treat k=1 separately using Cayley. But does the multipartite formula hold for k=1? For k=1, each part has size 1. The graph is complete n-partite with each part size 1, which is equivalent to the complete graph on n vertices (since no edges are missing? Actually if each part size 1, then there are no intra-part edges because each part has only one vertex, so no restrictions; edges between parts are all present. So it's the complete graph on n vertices. Number of spanning trees of K_n is n^{n-2} (Cayley). The multipartite formula: N = n (since k=1 => N = n). r = n (parts). Then formula: N^{r-2} ∏ (N - n_i)^{n_i -1}. Here N - n_i = n - 1, and n_i - 1 = 0, so each factor is (n-1)^0 = 1. So product =1. N^{r-2}= n^{n-2}. So it works if we interpret (0)^0 as 1? But (n-1) is not zero for n>1; n_i=1 so exponent 0. So fine. But note for n=1, r=1, N^{ -1} problematic. So base case n=1: For k=1, answer=1. For k>1, answer=0. So treat n=1 separately.
Also, need to consider n=2 and k=1? That's n=2, k=1: total nodes=2, number of trees on 2 labeled nodes = 1 (since 2^{0}=1). Our formula gives (2)^{0}=1; (k(n-1)=1*1=1; exponent n(k-1)=0; so 1. Works.
Now compute expression modulo MOD: ans = pow_mod(kn, n-2) * pow_mod(k(n-1), n*(k-1)) % MOD. But careful: For n=2, n-2=0, pow returns 1. For n=1, we treat separately. Also note for k=1, the second factor pow(k*(n-1), n*(k-1)) = pow(n-1, 0) = 1. So formula works for k=1 as well. So we could unify: For n>=2, ans = ( (kn)^(n-2) * (k(n-1))^(n*(k-1)) ) mod MOD. For n=1: if k==1 ans=1 else ans=0. But we must also check for n=1, k=1, ans=1. Input constraints n>=1, k>=1.
But wait: For k=2, n=1, ans=0 as per sample. For k=3, n=1, ans=0. So consistent.
But is there any nuance? The condition says: "Node i and node j are not adjacent, for all 0 <= i, j < k * n such that i div k = j div k". This means no edge between any two nodes from the same block. That's it. So the allowed graph is as described. So answer is spanning tree count.
But we must confirm: Are multiple edges allowed? No, simple tree. So counting spanning trees is correct.
Thus we need to compute ans mod MOD for n up to 1e5, k up to 3. The exponents: n-2 up to 1e5, n*(k-1) up to 21e5 when k=3. So exponent sizes are O(n). So we can compute using fast exponentiation O(log n) each, but careful: exponent values might be large but we can compute pow_mod(base, exponent, MOD) with exponent up to ~2e5, but exponent can be as large as n(k-1) ~ 2e5, still fine. But exponent is integer, we can use modular exponentiation.
But base: k*n can be up to 3e5, within MOD. So fine.
Now we need to consider modulo prime (1e9+7). Use pow_mod.
Edge case: For n=2, k=2, base second term: k*(n-1)=21=2, exponent n(k-1)=2*1=2, product=4. first term: 4^0=1. ans=4. Good.
Another test: n=2, k=3 => ans = (6)^0 * (3*(1))^{2*2}= (3)^{4}=81. That matches.
Now test n=3, k=2: ans = (6)^{1} * (22)^{31}=6 * (4)^3=6*64=384. Let's check by brute? Could be correct.
But wait: The sample with 4 1 gave 16 which matches n^{n-2} = 4^{2}=16.
Now we also need to consider n=2, k=1: ans = (2)^{0} * (11)^{20}=1 * 1^0 =1. Good.
All seems consistent.
Now we must be careful: The formula for complete multipartite graph with r parts requires r >= 2. So for n=1 we have r=1, which is a degenerate case. Our separate handling is fine.
But also need to consider n=0? Not allowed.
Now compute for large n. Since exponent may be negative for n=1? We handle.
Now complexity: O(log MOD) per exponent, which is fine.
But wait: The exponent n*(k-1) can be up to 2e5, which is fine.
But I recall that the formula may also be expressed differently. But I'm comfortable.
However, double-check the derivation: The number of spanning trees of complete multipartite graph K_{n1,...,nr} = (∑ n_i)^{r-2} ∏ (∑ n_j - n_i)^{n_i - 1}. Yes.
We have N = k n, and each n_i = k, so (N - n_i) = k n - k = k (n-1). So product = ∏_{i=1}^{n} (k(n-1))^{k-1} = (k(n-1))^{n (k-1)}. And (N)^{r-2} = (kn)^{n-2}. So ans = (kn)^{n-2} * (k(n-1))^{n (k-1)}.
This works for n>=2. For n=2, r=2, (kn)^{0}=1.
But wait: For n=2, (k(n-1)) = k. exponent n(k-1) = 2(k-1). So for k=2, it's (2)^{2}=4, for k=3, (3)^{4}=81, as we saw.
Now, but is there any condition on k? k up to 3. So fine.
Now we need to compute this modulo MOD.
But note: For k=1, the term (k(n-1)) = (n-1). But exponent n(k-1)=0, so it's 1. So (n-1)^0 = 1. But careful: if n=1 and k=1, we have separate case; for n=2, k=1: (n-1)=1^0=1, ok.
Now note: For n=2, k=1: (k(n-1)) = 1, exponent=0, so product=1; (kn)=2, exponent=0, so 1; ans=1. Good.
But there is also n=1, k=1: answer=1.
Now sample: Input 1 2 output 0. So separate.
Thus answer is straightforward.
But before finalizing, verify with some small cases by enumeration maybe? Let's try n=2,k=2 we have 4 trees. Let's list all spanning trees of K_{2,2} (complete bipartite with parts of size 2). The spanning trees of K_{2,2} correspond to choosing a spanning tree of 4 nodes that is bipartite between the parts. Actually any tree on 4 vertices with bipartition of size 2 each. Count should be 16? Wait number of labeled trees on 4 vertices total is 16. Among those, which ones have no edge within each part? The two parts: let's label nodes: part A: {0,1} (since blocks: indices 0,1 are block0? Actually with k=2, n=2, nodes 0,1 are block0, nodes 2,3 are block1. Condition: no edge within block0, no edge within block1. So allowed edges are between any node in block0 and any node in block1. So the graph is a complete bipartite between {0,1} and {2,3}. Spanning trees of K_{2,2}: There are 2^{2-1} * 2^{2-1}=2*2=4. So indeed only 4 of the 16 labeled trees satisfy condition. So good.
Now for n=3, k=2, we got 384. Could we compute total labeled trees on 6 nodes: 6^4=1296. Among them, those that satisfy the condition? Possibly 384 is plausible. We can verify quickly using known formula for complete bipartite? Wait for n=3, k=2 => 3 parts each size 2? Actually it's complete 3-partite graph with parts size 2 each. That is not bipartite. But number of spanning trees we computed as 384. Let's try to check using known results: number of spanning trees of K_{2,2,2} (octahedron graph?) Actually the complete 3-partite graph with parts size 2 each is the octahedron graph (the complement of a perfect matching?). The number of spanning trees of the octahedron graph is known to be 384? I recall the octahedron graph (which is the graph of the octahedron, vertices correspond to opposite pairs) has 384 spanning trees? Actually I recall that the octahedron graph (the 1-skeleton of an octahedron) has 8? Wait the octahedron has 6 vertices, each degree 4, and number of spanning trees is 384? That seems high. The octahedron graph has 6 vertices, number of spanning trees of the complete graph K6 is 6^4=1296. Octahedron graph is not complete; it's missing edges between opposite vertices? Actually octahedron graph: vertices: A1, A2, B1, B2, C1, C2? Wait typical octahedron: it can be seen as the complete multipartite graph K_{2,2,2}. Yes exactly. It is known that the number of spanning trees of K_{2,2,2} is 384? I think it is. I've seen that the number of spanning trees of the octahedron graph is 384. So consistent.
Now check n=3, k=3: total vertices 9. The complete 3-partite with each part size 3. Number we computed 9 * 6^{6}? Actually 9 * 6^{6}? Wait 6^{6}=46656, times 9 = 419904. That seems plausible.
Now we need to implement for n up to 1e5, k up to 3. Computation of exponent values can be done as long long. But careful: exponent n*(k-1) can be up to 2e5, which is fine.
But we must consider that pow_mod uses exponent as integer, which can be large but within 64-bit.
Now special case: For k=2, the second base k*(n-1)=2(n-1). For n=1, that base is 0. But we handle n=1 separately.
Also for n=2 and k=2, base=2(n-1)=2, exponent=2, fine.
Now note: For n=2, k=2, ans=4.
Now consider n=100000, k=3: ans = (300000)^{99998} * (3*99999)^{200000} mod MOD. That's huge but we can compute using modular exponent.
Now we need to compute pow_mod efficiently: O(log exponent). Since exponent up to 200000, log2(200k) ~ 18, so trivial.
But we must also consider modulus prime. Use iterative exponentiation.
But careful: When exponent is negative? Not.
Now there is also possibility of overflow when computing exponents as int. n up to 1e5, k up to 3, n*(k-1) up to 200000 fits in int.
Now we must handle n=1 for k=1: answer 1. For n=1 and k>1: answer 0.
Also edge: n=2, k=1: answer = 2^{0} * (1)^{0}=1.
But also n=2, k=1: nodes: two nodes, but condition: i div 1 = i, j div 1 = j, so condition applies only when i=j? Actually each block has size 1, so no internal edges. So all edges allowed? The graph is complete graph on 2 nodes, one edge possible. Spanning tree count = 1. Good.
Now also n=0? Not.
Thus solution: read n,k; MOD=1000000007; if n==1: if k==1 print 1 else print 0; else compute ans = pow_mod(kn % MOD, n-2) * pow_mod(k(n-1) % MOD, n*(k-1)) % MOD.
But we must be careful: For n=2, k=1, k*(n-1)=1, exponent n*(k-1)=0, pow_mod(1,0)=1. So fine.
Now test sample: Input: 4 1 => n=4,k=1; n>=2; base1=4, exp1=2 => pow=16; base2=13=3? Actually k(n-1)=13=3, exponent=4(0)=0 => pow=1; ans=16. Good.
Input: 2 2 => n=2,k=2; base1=4, exp1=0 =>1; base2=2*(1)=2, exponent=2*1=2 =>4; ans=4. Good.
Input: 1 2 => n=1, k=2, output 0. Good.
Thus solution is trivial.
But before finalize, consider that the formula may also require to treat the case when k=2 and n=1? Already done.
Now I should consider whether there is any nuance about the labeling: The nodes are labeled 0 to kn-1. The condition uses integer division by k. So indeed groups are contiguous blocks of size k. That yields the partition we used. So graph is K_{k,k,...,k} with n parts. Yes.
Now I want to double-check the derivation of the number of spanning trees for complete multipartite. It is known and can be proved using Kirchhoff's matrix tree theorem. So it's reliable.
Now I'll implement.
Pseudo:
mod = 1000000007 read n,k if n == 1: if k == 1: print(1) else: print(0) else: base1 = (k * n) % mod exp1 = n - 2 term1 = pow(base1, exp1, mod) base2 = (k * (n - 1)) % mod exp2 = n * (k - 1) term2 = pow(base2, exp2, mod) ans = (term1 * term2) % mod print(ans)
But we need to handle the case where base2 == 0 and exp2 == 0? For n=2, k=1: base2=11=1, exp2=20=0 => pow(1,0)=1. For n=2, k=2: base2=2*(1)=2, exp2=21=2 => pow(2,2)=4. For n=2, k=3: base2=31=3, exp2=22=4 => 81. So fine. For n=3, k=1: base2=12=2, exp2=30=0 => 1. For n=3, k=2: base2=22=4, exp2=31=3 => 64. So no zero base with zero exponent problematic (0^0). When could base2 be zero? For k>=1, n-1 could be zero only when n=1. But we already handled n=1 separately. For n=1, base2 = k0 = 0, exp2 = 1*(k-1) = k-1. For k>1, exp2>0, 0^(positive) = 0, but we don't compute because n=1 special case. For k=1, exp2=0, base2=0, 0^0 is ambiguous but we also handle n=1 separately. So we are safe.
Now check n=2, k=1: base2=11=1, exp2=20=0 => pow(1,0)=1.
Thus algorithm is correct.
But wait: For k=3, n=2: base2=31=3, exp2=22=4, ok.
Now we need to consider potential large exponents: n-2 up to 1e5, n*(k-1) up to 2e5. pow uses exponent as int, fine.
Now one more nuance: The formula for complete multipartite graph with all parts equal size k is sometimes given as: T = (kn)^{n-2} * (k(n-1))^{n(k-1)}. But is there any factor like division by something? No, it's a direct product. Confirm for small n,k:
Case n=3,k=2: T = (6)^{1} * (22)^{3} = 6 * 4^3 = 664=384. Could we compute with brute for small? Let's enumerate conceptually: graph has 6 vertices partitioned into 3 parts of size 2: part A={a1,a2}, B={b1,b2}, C={c1,c2}. Edges exist between any two vertices from different parts. That's a complete 3-partite graph. Number of spanning trees can be computed via matrix tree: Laplacian matrix L = diag(4,4,4,4,4,4) minus adjacency? Actually each vertex is adjacent to all vertices not in its own part, so degree = (kn - k) = 6-2=4. So each vertex degree 4. The Laplacian is 4I - A where A has 0 on diagonal, 1 if vertices in different parts. This matrix has known eigenvalues. One can compute number of spanning trees = (1/6) * product of non-zero eigenvalues? It yields 384. So likely correct.
Now check for n=4, k=2: T = (8)^{2} * (23)^{4} = 64 * (6)^{4} = 641296=82944. That might be correct.
Check for n=2, k=4? Not allowed.
Thus solution is simple.
But wait: k up to 3, but what about k=0? Not allowed.
Now the problem statement: "It is a tree with k * n nodes labeled from 0 to k * n - 1. Node i and node j are not adjacent, for all 0 <= i, j < k * n such that i div k = j div k". That's exactly the condition.
Thus answer as above.
Now we need to output number mod 1e9+7.
Thus solution.
Now but there is a twist: There might be another interpretation: Maybe the tree is not necessarily spanning tree? But it's a tree with k*n nodes, so it includes all nodes. So yes.
Now check complexity: O(1) arithmetic.
Now implement in code.
Potential pitfalls: Use long long for intermediate to avoid overflow? In Python it's fine. But in C++ we need to use modulo exponent.
We'll implement in C++ as follows:
long long MOD = 1000000007;
long long pow_mod(long long base, long long exp) { long long res = 1; base %= MOD; while(exp > 0) { if(exp & 1) res = (res * base) % MOD; base = (base * base) % MOD; exp >>= 1; } return res; }
int main() { int n, k; cin >> n >> k; if (n == 1) { if (k == 1) cout << 1 << endl; else cout << 0 << endl; return 0; } long long base1 = (1LL * k * n) % MOD; long long exp1 = n - 2; long long term1 = pow_mod(base1, exp1); long long base2 = (1LL * k * (n - 1)) % MOD; long long exp2 = 1LL * n * (k - 1); long long term2 = pow_mod(base2, exp2); long long ans = (term1 * term2) % MOD; cout << ans << endl; return 0; }
We need to ensure exp2 is non-negative. For k=1, exp2 = 0, ok.
Thus answer.
Now we should consider if there are any other edge cases like n=2,k=1 we covered.
Now test with sample: Input 2 2 => n=2 k=2, ans=4. Input 1 2 => 0. Input 4 1 => 16.
Now think about possible alternative interpretation: Could it be that the tree is not necessarily a spanning tree but any tree on that vertex set? But "a tree with kn nodes labeled from 0 to kn-1" means the tree uses all those nodes. So yes.
Now confirm with k=2, n=1: The condition says nodes 0 and 1 (both in same block) cannot be adjacent. So the only possible tree on 2 nodes must have edge between them, but it's forbidden, so 0. Our special case gives 0.
Now for k=1, n=1: only node 0, tree on 1 node (trivial). Number of trees on 1 node is 1. So output 1. Not given but plausible.
Now for n=1, k=1: but constraints n>=1, so possible. Should output 1.
Thus our solution covers.
Now is there any need for handling negative exponents? No.
Now final answer.
But I wonder if the problem expects us to derive this formula. With n up to 1e5, and k up to 3, it's trivial once formula known.
But we should double-check the formula's derivation for the case where parts are not all equal? Wait our parts are equal, but we used the general formula. The general formula is known, but maybe there is a subtlety: The graph is complete multipartite, but the Laplacian eigenvalues: one zero, each part contributes eigenvalues: N - n_i repeated (n_i - 1) times? Actually there is known eigenvalue pattern: For complete multipartite K_{n1,...,nr}, the Laplacian eigenvalues are: 0 with multiplicity 1, N (total vertices) with multiplicity r-1? Something like that. Actually the Laplacian matrix L = D - A. For complete multipartite, D = diag(N - n1 repeated n1 times, ...). And there are known eigenvalues: 0 (once), N (multiplicity r-1), and for each part i, N - n_i with multiplicity n_i - 1. So number of spanning trees = (1/N) * (product of nonzero eigenvalues) = (1/N) * N^{r-1} * ∏ (N - n_i)^{n_i-1} = N^{r-2} ∏ (N - n_i)^{n_i-1}. Yes, correct.
Thus formula is proven.
Now we can implement.
Now I think that's the answer.
But wait: There's something about labeling: The nodes are labeled from 0 to kn-1, and groups are determined by integer division by k. This means that groups are blocks of consecutive numbers? For example, with k=2, group0: 0,1; group1: 2,3; group2: 4,5; etc. So the partition is fixed. So the graph is exactly the complete multipartite with those parts. So yes.
Now we need to output result mod 1e9+7.
Now consider time: O(log exponent) trivial.
Now confirm with more tests:
n=3, k=2: ans=384. Let's compute quickly: (6)^(1)=6, (4)^(3)=64, product=384.
n=3, k=3: ans= (9)^(1) * (6)^(6) = 9 * 46656 = 419904.
n=4, k=2: ans= (8)^(2) * (6)^(4) = 64 * 1296 = 82944.
n=4, k=3: ans= (12)^(2) * (9)^(12) = 144 * (9^12 mod). 9^12 = (9^6)^2, etc. But we can compute mod. It's large but fine.
Now test n=5, k=2: ans= (10)^(3) * (8)^(5) = 1000 * 32768 = 32,768,000? Actually 10^3=1000, 8^5=32768, product=32768000. That seems plausible.
Now one more check: For n=2, k=2, ans=4, which is integer.
Now all good.
But could there be any other constraints? The problem is from some contest perhaps. With k up to 3, maybe there is a dynamic programming solution? But formula is easier.
Now we should also consider if we need to handle large n with exponent zero? For n=2, exponent1=0, base1=2k, term1=1. For n=2, exponent2 = 2*(k-1). For k=2, exp2=2, for k=3, exp2=4, for k=1, exp2=0.
Now done.
Now I'm convinced.
Now I'll produce final answer.
But before finalizing, let's check any potential overflow in C++ when computing base1 and base2: kn may be up to 300000, fits in int, but multiplication should be done with long long to avoid overflow before modulo. But we'll do 1LLk*n.
Now exp2 = n*(k-1) up to 200000 fits in int. So fine.
Now code.
But is there any need to treat modulo exponent when exponent is zero? pow_mod handles.
Now answer.
Now I'll produce final solution.
But hold on: The problem says "different good trees". Are trees considered distinct up to isomorphism? No, labeled trees, so each labeled tree is different. So indeed counting spanning trees on labeled vertices.
Thus final answer.
Now I'll produce explanation.
I'll also note that for n=1, the graph is empty if k>1, so no spanning tree.
Now output.
Now finalize. ```cpp
#include using namespace std;
const long long MOD = 1000000007;
long long pow_mod(long long base, long long exp) { long long res = 1; base %= MOD; while (exp > 0) { if (exp & 1) res = (res * base) % MOD; base = (base * base) % MOD; exp >>= 1; } return res; }
int main() { int n, k; cin >> n >> k;
// Special case n == 1 if (n == 1) { if (k == 1) cout << 1 << endl; else cout << 0 << endl; return 0; } long long base1 = (1LL * k * n) % MOD; long long exp1 = n - 2; long long term1 = pow_mod(base1, exp1); long long base2 = (1LL * k * (n - 1)) % MOD; long long exp2 = 1LL * n * (k - 1); long long term2 = pow_mod(base2, exp2); long long ans = (term1 * term2) % MOD; cout << ans << endl; return 0;}