# BIPIN3 - editorial

Author: Bipin Baburaj
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica

SIMPLE

### PREREQUISITES:

Fast modular exponentiation

### PROBLEM:

A rooted tree with N nodes is considered. We need to assign a color from 1 to K to each node of the tree in such a way that every pair of nodes (A,B), where A is the parent of B, has different colors.

### QUICK EXPLANATION:

The answer is K*(K-1)^{N-1}. Note that the actual tree is not given. This is because there is the same answer for every tree with N nodes (and for the given K).

### EXPLANATION:

We can choose any of the K colors for the root of the tree. Then we can choose any color except the root’s color for any of the root’s children. Then, for every child of a child of the root we can choose any color except that of its parent, and so on. Thus, for each of the other N-1 nodes we have K-1 choices for its color. The overall answer is K*(K-1)^{N-1}.

For subtasks 1 and 2 one can compute the answer in O(N) time. For subtask 3 one needs to compute (K-1)^{N-1} (modulo 10^9+7) using fast modular exponentiation, in O(log(N)) time.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

I have two solutions for the same problem. I applied the exponentiation by squaring method but got a TLE for the use of `fmod` instead of `%`. Can anyone explain me why the use of fmod gives a wrong answer but the use of % gets me an AC?
My custom _fmod function reads something like ::

``````    uint64_t _fmod(uint64_t x, uint64_t y)
{
#pragma STDC FENV_ACCESS ON
uint64_t result = std::remainder(std::fabs(x), (y = std::fabs(y)));
if (std::signbit(result)) result += y;
return std::copysign(result, x);
}
``````

My accepted solution uses the `%` operator but I was hoping to get around the `_fmod()` function which is nothing but a variant of C++ `fmod` method.

#include<studio.h>

//