先把 $1,2,3$ 连成一个三元环，并钦定它们的颜色分别为 $1,2,3$。转化为要求其余点的染色方案数恰好为 $k$。再用 $8$ 个点依次连向 $3,1,2,3,1,2,3,1$，这样它们能选的颜色分别为 $(1,2),(2,3),(3,1),\ldots$。再把这 $8$ 个点连成一条链，这样它们的染色方案一定是一个前缀选能选的第一种颜色，其余的选第二种颜色。另外留 $8$ 个孤立点，之后会用到。

如果在这 $8$ 个点上每个点 $3+i$ 再连上 $a_i$ 个点，并且这 $a_i$ 个点都连上 $3+i$ 的第一种颜色，那么如果 $3+i$ 选的是第一种颜色，方案数会乘以 $2^{a_i}$。因此总的方案数是 $1+2^{a_1}+2^{a_1+a_2}+\cdots$。

对于给定的 $k$，首先如果 $k$ 是偶数，则连一个叶子到 $1$，并把 $k$ 除以 $2$。现在 $k$ 是奇数，设 $\mathrm{popcount}(k)=b$，则将 $3+b$ 和它的第一种颜色连边，那么就只有前面的 $b-1$ 个点可以变化，按上文所述在每个点上再连若干个点，便能构造出我们需要的 $b$ 个位。这样额外用到的点数是 $\lfloor\log_2k\rfloor\le 8$，额外的孤立点同时向 $1,2$ 连边即可，总共连的边数不超过 $8\cdot 2+1=17$。