中世紀是一個黑暗的世紀。農夫約翰的奶牛們總是喜歡在吃草的時候找個伴聊天。而奶牛們吃草的地方，是一個用籬笆圍成一個凸多邊形的草地，所謂的凸多邊形，就是這個多邊形上所有頂點的內角都小於180度的簡單多邊形。每天早晨，農夫約翰都會把奶牛們帶到這片草地，而每一隻牛都有自己喜歡吃草的位置，在吃草的過程中，籬笆圍繞範圍裡面的奶牛們可以兩兩找個伴聊天，悠閒地度過一整天。

好景不常，中世紀是一個黑暗的世紀。嚴格的「草地管制機關」實施了一項新的政策「籬笆三角化政策」。農夫約翰必須增設一些籬笆，使得切割出來的每一個區域都是三角形。這些新增設的籬笆必須從凸多邊形的頂點直線連到另一個頂點，而且它們不能在草地內部相交。

為了配合政策，但是又不能讓吃草的奶牛們找不到伴聊天。農夫約翰架設的籬笆必須使每一個三角形的區域內一定會有偶數隻奶牛。請你幫忙算算看，農夫約翰究竟有多少種三角化這片凸多邊形區域的方法呢？由於答案可能很大，你只要輸出答案除以M的餘數就可以了。
請注意，新架設的籬笆必須是直線段，而且不能有任何奶牛吃草的位置在上面。