P3587 [POI 2015] POD

长度为 $n$ 的一串项链，每颗珠子是 $k$ 种颜色之一。第 $i$ 颗与第 $i-1,i+1$ 颗珠子相邻，第 $n$ 颗与第 $1$ 颗也相邻。 切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。 求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

无

无

**【样例解释】** 四种方法中较短的一条分别是 $(5),(4),(1,1),(4,1,1)$。相差最小值 $6-3=3$。 ---- 原题名称：Podział naszyjnika。