TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

52.4% (11/21)

Submission's AC Ratio

12.8% (18/141)

Description

好熱啊
隨著地球暖化,現在夏天越來越熱
沒有開窗戶根本就受不了
在祕密的教室裡,有$N \times M$ 個窗戶形成 $N, (2 \leq N \leq 16) \times M, (2 \leq M \leq 16)$ 的平面
因為實在太熱了,所以你知道對於每一個 $2 \times 2$ 的窗戶們,至少要有兩個窗戶是打開的,不然全班都會熱死。
先不要管為什麼不全部打開,班上最軟的蛋餅忽然問你,有多少種開窗戶的方法能讓班上不熱死呢?
為了成功玩到蛋餅的肚子,你決定趕快告訴他有幾種方法。

由於可能的方法太多了,所以蛋餅希望你告訴它方法數量除以 $K (2 \leq K \leq 10^ 9 + 9)$ 的餘數就好了

Input Format

第一行有三個正整數 $N\ M\ K$ 以一個空白隔開,意義如題目所述

Output Format

請輸出一個介於 $[0, K)$ 的整數,代表答案

Sample Input

2 2 100

Sample Output

11

Hints

小心 overflow 喔 xddddd
記得模運算很慢喔 ><><><>

關於範測一
以xx方格表示關閉的窗戶,....方格表示開啟的窗戶
則下圖為所有合法的開窗戶方法

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0 $N, M \leq 2$ 1
2 0~5 $N, M \leq 4$ 19
3 0~13 $N, M \leq 8$ 20
4 0~21 $N, M \leq 12$ 25
5 0~29 $N, M \leq 16$ 35

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 65536 65536 1 2 3 4 5
1 500 65536 65536 2 3 4 5
2 500 65536 65536 2 3 4 5
3 500 65536 65536 2 3 4 5
4 500 65536 65536 2 3 4 5
5 500 65536 65536 2 3 4 5
6 500 65536 65536 3 4 5
7 500 65536 65536 3 4 5
8 500 65536 65536 3 4 5
9 500 65536 65536 3 4 5
10 500 65536 65536 3 4 5
11 500 65536 65536 3 4 5
12 500 65536 65536 3 4 5
13 500 65536 65536 3 4 5
14 500 65536 65536 4 5
15 500 65536 65536 4 5
16 500 65536 65536 4 5
17 500 65536 65536 4 5
18 500 65536 65536 4 5
19 500 65536 65536 4 5
20 500 65536 65536 4 5
21 500 65536 65536 4 5
22 1000 65536 65536 5
23 1000 65536 65536 5
24 1000 65536 65536 5
25 1000 65536 65536 5
26 1000 65536 65536 5
27 1000 65536 65536 5
28 1000 65536 65536 5
29 1000 65536 65536 5