题目描述

小q现在在买饲料的路上，到达卖饲料的地方后小q还需要再上 $n$ 级台阶。小q的步子可以很大，每次小q可以上 $1$ 或 $2$ 或 $3$ 级台阶。

由于今天下雨了，有一些台阶上有积水。但是小q穿的今天新买的AJ，为此他不想新鞋踩到水上，所以他不愿意走到有积水的台阶上。

小q现在想知道：在不走到有积水的台阶上的情况下，走到第n级台阶有多少种不同的走法。由于答案可能很大，你只需要输出不同的走法数量对 $10007$ 取模。

输入格式

第一个整数 $n$，表示台阶数量。

接下来 $n$ 个数，第 $i$ 个数为 $0$ 表示第 $i$ 级台阶有积水，第 $i$ 个数为 $1$ 表示第 $i$ 级台阶没有积水。

数据保证第 $n$ 级台阶上一定没有积水（不必验证）。

输出格式

输出一个数，表示不同的走法数量对 $10007$ 取模的结果。

如果小q无法在不走到积水的台阶的条件下走到第 $n$ 级台阶，则输出 $0$。

---

本人对判断积水这一块比较迷茫，请大佬指教！