A farm has n barns numbered 1..n, joined by n - 1 paths so that every barn is reachable (a tree). Each barn gets one of 3 colours, 1, 2 or 3, and two barns joined by a path must get different colours. Some barns are already painted and can't be changed.
Write count_colorings(n: int, edges: list[tuple[int, int]], painted: list[tuple[int, int]]) -> int: the number of valid ways to colour all barns, modulo 10**9 + 7. painted lists (barn, colour) pairs, each barn at most once.
Examples:
count_colorings(3, [(1, 2), (2, 3)], []) == 12: barn 2 has 3 choices, then barns 1 and 3 have 2 each.count_colorings(3, [(1, 2), (2, 3)], [(1, 1), (3, 2)]) == 1: barn 2 must be colour 3.count_colorings(2, [(1, 2)], [(1, 3), (2, 3)]) == 0
Constraints: 1 <= n <= 100_000. The tree can be a single long path of 100k barns, so a recursive DFS will blow Python's recursion limit: walk the tree with an explicit stack (or BFS order) and process nodes children-first. Aim for O(n).
Show hint
Root the tree anywhere. For each barn, count the valid colourings of its subtree separately for each colour the barn itself could take.