解题思路
每格有 26 种色号，唯一限制是不能出现连续四格同色。按「当前结尾已经连续同色几格」分类计数，再对所有询问查表。
- 记 f1(i)、f2(i)、f3(i) 为长度 i、结尾恰好连续 1、2、3 格同色的方案数，合法总数 g(i)=f1(i)+f2(i)+f3(i)。
- 第 i 格换一种与上一格不同的色号时，结尾连续变成 1，有 f1(i)=25⋅g(i−1)。
- 把结尾的一连、两连再涂一格相同色，分别得到 f2(i)=f1(i−1)、f3(i)=f2(i−1)。已经三连的不能再同色延长，否则会出现四连。
- 起点 g(1)=26。询问很多且长度上界固定，先预处理出所有 g(1)∼g(200000)，每个询问 O(1) 作答。答案对 1000000007 取模。
