难点在于卡 __int128（？）。
首先 \(N>K\) 显然无解，只需考虑 \(N\le K\) 的情况。然而这并没有什么用。
把 \(b\) 看作集合，显然 \(b_i\subset b_{i+1}\)。所以令 \(f_{n,i}\) 为考虑到 \(b_n\) 且 \(|b_n|=i\) 的方案数，集合元素无序，即选择 \(\{A,B,C\}\) 或者 \(\{A,B,D\}\in \{A,B,C,D\}\) 看作不同方案，且不考虑其它 \(k-i\) 种元素。有如下转移：
\[f_{n,i}=\sum\limits_{j=0}^if_{n-1,i-j}\dbinom{i}{j}2^{i-j} \]即考虑 \(b_n\setminus b_{n-1}\) 的大小，从 \(b_n\) 中有的选出 \(|b_n\setminus b_{n-1}|\) 个一定要选，另外 \(|b_{n-1}|\) 个元素对于 \(a_n\) 可以任意选择。
把转移形式写得好看一点：
\[f_{n,i}=\sum\limits_{j=0}^if_{n-1,i}\dbinom{i}{j}2^j \]\[\text{ans}=\sum\limits_{i=1}^{K}f_{N,i}\dbinom{K}{i} \]注意到 \(f\) 的转移组合数拆开后可以写成卷积的形式，于是我们有了 \(O(NK\log K)\) 的做法，然而这还是没有什么用。
但是注意到，\(f_{n}\) 其实能从任意的 \(a+b=n\) 转移而来，具体地：
\[f_{n,i}=\sum\limits_{j=0}^if_{a,j}f_{b,i-j}\dbinom{i}{j}2^{bj} \]原理是类似的，考虑 \(b_n\) 和 \(b_a\) 的关系，枚举 \(b_a\) 的大小，从 \(i\) 个元素中选出 \(j\) 个来自 \(b_a\)，剩下 \(b_{a+1}\setminus b_a,b_{a+2}\setminus b_a,\cdots ,b_{n}\setminus b_a\) 这些集合显然也满足前面是后面的子集，于是对这 \(b\) 个集合，用 \(f_{b,i-j}\) 枚举这样的集合序列的方案数，最后这些集合对于 \(b_a\) 中原本有的元素都可以任意挑选。
然后就是套路了，令 \(a=\left\lfloor\dfrac{n}{2}\right\rfloor\)，\(b=\left\lceil\dfrac{n}{2}\right\rceil\)，分治求解即可。复杂度 \(O(K\log K\log N)\)。
要写任意模数 NTT，不能 #define int __int128。
彩蛋：
(官方题解：)We decided to ask the answer modulo \(10^9+7\) to not let the participants easily guess that these problem requires FFT
标签：ch,Sequence,Transforming,res,CF623E,poly,int,Mul,size From： https://www.cnblogs.com/Ender32k/p/17585748.html