You are given a tree that contains vertices and queries. Each query is determining the number of decompositions of the tree into paths and the path from to that is one of the paths in the decomposition modulo 998244353.

A tree decomposition in paths is valid if each vertex belongs to exactly one path. A path can be a single vertex. Two decompositions are different if there are two vertices and that belong to the same path in one of the decompositions but two distinct paths in the other.

Sample Input:

5 2 3 1 4 1 1 5 2 5 3 3 2 5

Output :

8 4

Can anyone please explain this problem with an example... Problem Link : https://www.hackerearth.com/problem/algorithm/path-decomposition-ii-ad4b4a0c/

Problem Link : https://www.codechef.com/ENFE2020/problems/ECFEB207

Problem : Chef bought a rectangular checkered board of size N rows and M colums and color pens of P different colors. He randomly painted each cell with any of the P colors. When he was done painting all the cells, he noticed something very interesting property. For any vertical line that divides the board into two non-empty boards, the number of distinct colors in both the parts was the same.

Now, chef wonders in how many ways can he color the board using only the colors available such that this interesting property holds.

1≤N,M≤1000 1≤P≤10^6

Output : print the answer to the problem modulo 1000000007.

E.g. INPUT : 2 2 2 OUTPUT: 8

My Approach: I think, we can decide some colours which are to be arranged in the first column, and then each of the selected colour should be present in the last column at least once in any order , and the rest of the (N) X (N-2) matrix can have any distribution with these selected colours, because now,no matter wherever we draw a vertical line , number of distinct colours in the two parts will be same…I couldn’t implement it. Can anyone please let me know, if this approach is correct and how can I implement it. Or suggest some better approach…