{"problem":{"name":"[集训队互测 2023] 基础寄术练习题","description":{"content":"对于长度为 $n$ 的序列 $a$，定义 $f(a)=\\dfrac{1}{\\prod\\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\\{a_n\\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\\le k\\le 2$**。 考虑所有满足以下三个条件的序列 $a$： - $a$ 的长度为 $n$。 - $\\forall i,j$，$a_i\\ne a_j$。 - $1\\le a","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10005"},"statements":[{"statement_type":"Markdown","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$ 是一个质数。\n\n## Input\n\n第一行四个整数 $n,m,k,p$，分别代表序列长度，序列元素的上界和模数。\n\n## Output\n\n一行一个整数表示答案对 $p$ 取模后的结果。\n\n[samples]\n\n## Note\n\n对于所有数据，保证 $2\\le n\\le m\\le 100$，$10^8