## Problem Links:

**Author : **Aman Kedia

**Tester : ** Himanshu Jaju

**Editorialist : ** Aman Kedia

## Difficulty:

Medium

## Explanation

Let us assume that there are x distinct coloured balls with chef and Bakku initially (leaving special balls). Now let y be the number of colors common between the balls of chef and bakku.

If we can find solution for a fixed value of x and y then we can iterate over possible values of x and y for the total number of ways.

For a fixed value of x and we can find number of ways to color N balls with chosen x colors using the following recurrence:

dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1]

To calculate number of ways we need to multiply the dp[n][x]^{2} by number of ways of choosing these x colors for coloring simultaneously keeping y colors common between both selection of x colors.

So the number of ways for coloring 2*N balls will be C(K,2*x-y)* C(2*x-y, x)* C(x,y)*dp[n][x]^{2}

Now we can colour two special balls in 3 ways:

- We can color both of them with any of K-(2*x-y) colors so that both chef and bakku have x+1 distinct colored balls after any distribution.
- Color both of them with any of y common colors so that both chef and bakku have x+1 distinct colored balls after any distribution.
- Color one with any of (x-y) colors that only chef has and other with any of (x-y) colors that only bakku has. Now for one distribution both of them will have x distinct balls and for other both of them will have x+1 distinct balls.