題目連結：
題目大意：
給定兩正整數 ｎ 、 ｍ （１ ≦ ｎ ≦ １０, ０００, ０００ 、 １ ≦ ｍ ≦ １, ０００, ０００, ０００），代表有 ｎ 件工作，編號依序為 １ ～ ｎ 。
而現在 Ｌ 小姐想完成這 ｎ 件工作。但是按照她的個性，當完成了編號為 ｉ 的工作，一定不會緊接著去完成第 ｉ ＋ １ 個工作。
求 Ｌ 小姐有多少方法（順序）完成這 ｎ 件工作。將方法數取除以 ｍ 的餘數。
範例輸入：
輸入範例1：
3 1000
輸入範例2：
4 7
範例輸出：
輸出範例1：
3
輸出範例2：
4
解題思維：
典型的數學上之遞迴的問題，也是程式解題經典的動態規劃題。
假設已經知道完成 ｉ 件和 ｉ － １ 件工作的方法數（以下稱 Ｄｉ 、 Ｄｉ － １ ），則我們可以觀察出 ｉ ＋ １ 件工作的方法數有以下的規律：
當第 ｉ ＋ １ 件工作不是第 ｉ ＋ １ 個完成時，我們可以從剩下的 ｉ 件工作選出 ｉ 個縫隙去插入這個工作（已扣除最後的位置）。因此有 Ｄｉ × ｉ 種方法。
而第 ｉ ＋ １ 件工作是第 ｉ ＋ １ 個完成時，第 ｉ 個工作不能是第 ｉ 個完成的（會跟規則衝突）。與上同理，會有 Ｄｉ － １ × （ｉ － １）種方法。
因此我們總合以上的可能性，得出：
Ｄｉ ＋ １ ＝ Ｄｉ × ｉ ＋ Ｄｉ － １ × （ｉ － １）。
且已知 Ｄ１ ＝ １ 、 Ｄ２ ＝ １ ，因此我們可以推得 Ｄｎ 。剩下的就只要每次做運算時，去取 ｍ 的餘數即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
