P3448 [POI 2006] MIS-Teddies

Byteoian 是一家专业生产儿童玩具的公司。他们生产的玩具质量上乘，广受好评。 但最近，有人发现他们生产的泰迪熊存在致命缺陷。总共有四种泰迪熊型号：$A1$，$A2$，$B1$，$B2$，一旦将三个字母相同或数字相同的泰迪熊放在一块，就会对泰迪熊造成致命损坏。 如果一种摆放泰迪熊的方案中不存在连续三个字母相同或数字相同的泰迪熊，则称这种摆放方案是**安全的**。 现在你收集了一些泰迪熊，你想要知道有多少种安全的摆放泰迪熊的方案。由于安全的方案可能较多，请输出方案数对 $1\,000\,000$ 取模的结果。

无

无

$0 \leq n_{A1},n_{A2},n_{B1},n_{B2} \leq 38$。