#CW20. 序列计数(count)

序列计数(count)

题目描述

给定正整数 nn 和非负整数 dd,符合如下条件的由 {A,B,C}\{A,B,C\} 组成的、长度为 nn 的字符串,称为合法字符串:

  • 不能存在两个连续的 AA 或 CC,不能存在 33 个连续的 BB;
  • 设 A,B,CA,B,C 的出现次数分别为 a,b,ca,b,c,则其中任意两个数之差的绝对值都不得超过 dd;
  • 该字符串不能是回文串,也就是将该字符串整体翻转后,不能和原字符串相同。

请你求出合法字符串的数量。你只需要输出合法字符串数量对 2642^{64} 取模的结果。

输入格式

第一行包含两个整数 n,dn,d。

输出格式

输出一个整数,表示合法字符串的数量对 2642^{64} 取模后的结果。

样例 1 输入

3 0

样例 1 输出

6

样例 2 输入

4 1

样例 2 输出

24

数据范围

对于所有测试数据,保证:2≤n≤2002 \le n \le 200,0≤d≤100 \le d \le 10。

测试点 n≤n \le d≤d \le
1∼41 \sim 4 1212 1010
5∼75 \sim 7 2020
8∼108 \sim 10 2525 22
11∼1511 \sim 15 5252 1010
16∼2016 \sim 20 200200