Раскраска дерева в 3 цвета с фиксированными вершинами

Дано дерево из n вершин (0..n-1), заданное n-1 рёбрами edges, и массив fixed длины n: fixed[i] = 0 означает, что цвет вершины i свободный, fixed[i] = 1/2/3 - вершина i обязана быть именно этого цвета. Посчитайте число способов раскрасить ВСЕ вершины в 3 цвета так, чтобы соседние по ребру вершины были разного цвета и все зафиксированные ограничения выполнялись. Ответ верните по модулю 1000000007. Решается обходом дерева снизу вверх: для каждой вершины и каждого её возможного цвета считается число раскрасок поддерева.