首先看到這題的時候，我們可以知道 $n$ 種顏色選 $i$ 種顏色有 $C_i^n$ 種取法，每個居民有 $i$ 種顏色可以挑，所以最後的答案就是 $\sum\limits_{i = 1}^{n} i^c \times C_i^n$。
當 $n \leq 10^6$ 時，可以使用快速冪 $O(n\times\log(n))$ 加總。
當 $n$ 很大時我們就必須要把式子化簡，根據二項式定理 $(1 + x)^n = C_0^n \times x^0 + C_1^n \times x^1 + \dots + C_n^n \times x^n$。
我們令 $f_0(x) = (1 + x)^n = C_0^n \times x^0 + C_1^n \times x^1 + \dots + C_n^n \times x^n$，$f_i(x) = 1^i\times C_1^n \times x^1 + 2^i \times C_2^n \times x^2 + \dots + n^i\times C_n^n \times x^n = \sum\limits_{j = 1}^{n} j^i\times C_j^n \times x^j$，答案就會是 $f_c(1)$。
那要怎麼把 $f_{i-1}(x)$ 變成 $f_i(x)$ 呢？可以注意到對 $f_{i-1}(x)$ 一次微分後，$x$ 的次數會少 $1$，$j^{i-1}$ 會變成 $j^i$，那為了維持 $x$ 的次數，微分後再乘一個 $x$，於是得出 $f_i(x) = xf'_{i - 1}(x)$。
那現在就可以把式子變成 $(1 + x)^n$ 一直微分一直乘 $x$ 了，現在就要來觀察微分後式子的性質：
\[f_1(x) = n\times x \times (1 + x)^{n - 1}\]
\[f_2(x) = n\times\ x \times (1 + x)^{n - 1} + n\times (n - 1) \times x^2 \times (1 + x)^{n - 2}\]
\[f_3(x) = n\times x \times (1 + x)^{n - 1} + 3\times n \times (n - 1) \times x^2 \times (1 + x)^{n - 2} + n\times (n - 1) \times (n - 2) \times x^3 \times (1 + x)^{n - 3}\]
\[f_4(x) = \frac{n!}{(n-1)!}\times x \times (1 + x)^{n - 1} + 7\times \frac{n!}{(n-2)!} \times x^2 \times (1 + x)^{n - 2} + 6\times \frac{n!}{(n-3)!} \times x^3 \times (1 + x)^{n - 3} + \frac{n!}{(n-4)!} \times x^4 \times (1 + x)^{n - 4}\]
我們可以得出 $f_i(x) = \sum\limits_{j = 1}^{i} a_{i, j} \times \frac{n!}{(n-j)!} \times x^j \times (1 + x)^{n - j}$，後面三個東西可以很快求出來，但是前面那個 $a_{i, j}$，你知道這是什麼嗎？你相信這個奇怪的小東西在這一題或許是最難求的嗎？
觀察微分的規律，可以知道 $a_{i, j} = a_{i - 1, j - 1} + j\times a_{i - 1, j}$，這樣直接求的話要 $O(c^2)$ 才行，正當苦惱的時候，維基百科上面就有這個東西，這又叫第二類史特靈數，而這個可以表示成 $a_{i, j} = \frac{1}{j!}\sum\limits_{k = 0}^{j} (-1)^k \times C_k^j \times (j - k)^i$，而可以化簡成 $\sum\limits_{k = 0}^j \frac{(-1)^k}{k!} \times \frac{(j - k)^i}{(j - k)!}$，而這個形式越看越像可以 $\text{NTT}$，也就是 $O(N\times log(N))$ 多項式乘法之類的東西 (可以在這題或這題) 練習。
只是這題要模的是 $10^9 + 7$，很難去 $\text{NTT}$，因為 $10^9 + 6$ 以二進制表示只有一個後綴 $0$，那要怎麼辦呢？這題多項式乘法過後，數字最大可以到 $10^5\times 10^9 \times 10^9 = 10^{23}$，於是至少要用三個適合 $\text{NTT}$ 的模數，做完 $\text{NTT}$ 之後，用中國剩餘定理求出那個數字，再對 $10^9 + 7$ 取模，並且過程中也許會用到 $\text{__int128}$。
找完 $a_{i, j}$ 之後，我們就能計算 $f_c(1)$ 了，$f_c(1) = \sum\limits_{j = 1}^{c}a_{c,j}\times \frac{n!}{(n-j)!}\times 2^{n - j}$，$n$ 會是一個很大的數，那可以令 $n_1≡n\ (\bmod 10^9 + 7),\ n_2≡n\ (\bmod 10^9 + 6)$，那答案就是 $\sum_{j = 1}^{c}a_{c,j}\times \frac{n_1!}{(n_1-j)!}\times 2^{n_2 - j}$，簡直好到不真實！