T296829 入门 T4 - 染色

有 $n$ 颗珠子，从左到右排成一行。 你想给它们染上颜色，共有红、蓝、黄三种颜色可选，分别需要染 $a,b,c$ 颗（$a+b+c=n$）。 假设第 $i$ 颗珠子染的颜色是 $d_i(1\le i\le n)$，那么你应该保证 $d_i\neq d_{i+1},d_1\neq d_n$。 求染色的方案数，对一个给定的模数取模。

一行，四个整数，$a,b,c,mod$。其中 $mod$ 表示模数。

一行，一个非负整数，表示答案。 你应当保证它在 $[0,mod)$ 范围内。

【数据范围】 本题为捆绑测试。 Subtask 1（10分）：$n\le 11$ Subtask 2（10分）：$a,b,c\le 50$ Subtask 3（4分）：$a,b\le 10^7,c=0$ Subtask 4（20分）：$a,b,c\le 150$ Subtask 5（25分）：$a,b,c\le 300$ Subtask 6（30分）：$a,b,c\le 1000$ Subtask 7（1 分）：$a,b,c\le 10^7$，保证 $mod$ 为质数 对于所有数据，$10^8\le mod\le 10^9+100,2\le n=a+b+c$ 【时间限制】 前 $6$ 个 Subtask 为 $1s$，第 $7$ 个 Subtask 为 $3s$。