{"raw_statement":[{"iden":"statement","content":"对于长度为 $n$ 的序列 $a$，定义 $f(a)=\\dfrac{1}{\\prod\\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\\{a_n\\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\\le k\\le 2$**。\n\n考虑所有满足以下三个条件的序列 $a$：\n\n- $a$ 的长度为 $n$。\n- $\\forall i,j$，$a_i\\ne a_j$。\n- $1\\le a_i\\le m$。\n\n求它们的 $f(a)$ 之和，答案对 $p$ 取模。保证 $p$ 是一个质数。"},{"iden":"input","content":"第一行四个整数 $n,m,k,p$，分别代表序列长度，序列元素的上界和模数。"},{"iden":"output","content":"一行一个整数表示答案对 $p$ 取模后的结果。"},{"iden":"note","content":"对于所有数据，保证 $2\\le n\\le m\\le 100$，$10^8<p<1.07\\times 10^9$ 且 $p$ 为质数，$1\\le k\\le 2$。\n\n- Subtask 1 (10 pts)：$m\\le 20$。\n- Subtask 2 (25 pts)：$k=1$。\n- Subtask 3 (15 pts)：$n=m\\le 30$。\n- Subtask 4 (10 pts)：$m\\le 30$。\n- Subtask 5 (15 pts)：$m\\le 40$。\n- Subtask 6 (10 pts)：$m\\le 70$。\n- Subtask 7 (15 pts)：$m\\le 100$。"}],"translated_statement":null,"sample_group":[["2 3 2 1000000007","966666675"],["3 5 2 998244353","148276980"],["6 10 2 1004535809","622165218"],["15 20 2 1064822107","53789887"],["30 40 1 265371653","179937201"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}