P4804 [CCC 2016] 生命中的圆

**译自 [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T5「[Circle of Life](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)」** > 也许你听说过康威生命游戏（Conway's Game of Life）。康威生命游戏适用于方格组成的矩阵。但它可以产生十分复杂的结构。在这道题目中，我们将使用简化版的生命游戏来虐你。 这个游戏是 0 人游戏，换句话说，只要给定初始条件，这个游戏就能自己进行下去。 将一个圆环分为 $N$ 段，将这 $N$ 段顺时针依次编为 $1,\dots,N$ 号。每一段要么是活的（以 `1` 表示），要么是死的（以 `0` 表示）。 游戏会进行 $T$ 轮「变化」。如果一个方格**恰好**有一个相邻的方格在这次变化中存活，那么该方格会在下次变化中存活。否则，该方格会死亡。 给定圆环的初始状态，求经过 $T$ 次变化之后的状态。

无

无

#### 样例解释 1 方格 $1$ 和 $N - 1$ 和 $N$ 相邻，因此在一次变化后仍存活。 #### 样例解释 2 一次变化后，状态为 ` 00011`。 两次变化后，状态为 ` 10111`。 对于 $\frac{1}{15}$ 的数据，$N \le 15,T \le 15$。 对于另外的 $\frac{6}{15}$ 的数据，$N \le 15$。 对于另外的 $\frac{4}{15}$ 的数据，$N \le 4000,T \le 10\ 000\ 000$。 注意对于所有的数据，你需要使用 64 位整数。