玄关

棋子排成一排，并且规定白棋不能单独摆放。换句话说，要么没有白棋，要么不止一个白棋摆在一起。比如4个棋子，有7种可能的合法摆法（W白棋，B 黑棋）：WWWW, WWWB, BWWW, WWBB, BWWB, BBWW, BBBB。

给定要摆放的棋子数量，求所有可能的合法摆放种数。结果可能很大，对100000007取模后输出。

对于30%的数据，1≤n≤15 对于 100% 数据：1≤n≤500000。