貴最喜歡賽馬娘了！

其中貴又有 \(N\) 個喜歡的賽馬娘排列樣式。

賽馬娘有什麼好排列的呢？你可能會問。

就讓貴來教教你世間的正道吧！

儘管賽馬娘都是母的，不過賽馬娘的前世有公的也有母的，而貴正是能一眼看出賽馬娘前世性別的男人。

對於每種 \(M\) 隻賽馬娘的排列，貴都會用他喜歡的 \(N\) 個排列樣式來檢驗它。

只有符合其中至少 \(\frac{NP}{Q}\) 個排列樣式的馬娘排列才能獲得貴的認證。

每個排列樣式都形如一個長度 \(M\) 的字串，且每個字元都是 0 、1 或 ? 中的一個。

第 \(i\) 個字元是 0代表在這個排列樣式中貴希望第 \(i\) 隻賽馬娘的前世性別是公的，

第 \(i\) 個字元是 1代表在這個排列樣式中貴希望第 \(i\) 隻賽馬娘的前世性別是母的，

第 \(i\) 個字元是 ?代表在這個排列樣式中貴對第 \(i\) 隻賽馬娘的前世性別沒有限制。

而對於每個排列樣式，只要賽馬娘的排列中有任何一個位置的賽馬娘的前世性別和貴所希望的一樣（必須是字串中不是 ?的位置），貴就會感到滿意並將該排列視為符合排列樣式。

特別的，對於全部字元都是 ?的排列樣式，所有排列都是符合的。

現在，貴想知道所有 \(M\) 隻賽馬娘排列對應到她們前世的公母排列中（總共有 \(2^ M\) 種），有幾種是能獲得貴的認證的呢？（符合至少 \(\frac{NP}{Q}\) 個排列樣式）

請你告訴貴這個問題的答案吧！（你肯定不會讓貴失望的吧？）