#P6839. 喵喵国的游走

    ID: 6671 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-组合数学贡献法双射计数概率与期望期望线性性动态规划计数 DPPascal 递推构造与建模奇偶性分析滚动数组CF2400

喵喵国的游走

喵喵国的游走

题目描述

喵喵国是一个无限大的 kk 维整数格点空间。犬犬从原点 (0,0,…,0)(0,0,\ldots,0) 出发,每一步等概率地选择 2k2k 个方向之一:选择一个坐标,将它增加 11 或减少 11。

走完 nn 步后,求犬犬经过的不同位置的数量的期望 EE。起点也计入经过的位置,同一位置被多次经过只计一次。

例如,路径 (0,0)→(0,1)→(1,1)→(1,0)→(0,0)(0,0)\to(0,1)\to(1,1)\to(1,0)\to(0,0) 经过了 44 个不同位置。

为避免分数,输出 E(2k)n mod modE(2k)^n\bmod\mathrm{mod}。这个乘积是整数,模数不保证为质数。

输入格式

输入三个正整数 n,k,modn,k,\mathrm{mod}。

输出格式

输出一个整数,表示 E(2k)n mod modE(2k)^n\bmod\mathrm{mod}。

样例输入 1

4 2 123456789

样例输出 1

1068

样例输入 2

30 2 1000000000

样例输出 2

842235648

样例输入 3

50 5 876543210

样例输出 3

519048580

数据范围

  • 对于 10%10\% 的数据,n≤5n\le5。
  • 另外 20%20\% 的数据,k=1k=1。
  • 另外 20%20\% 的数据,n≤50n\le50 且 k≤2k\le2。
  • 另外 20%20\% 的数据,k=2k=2。
  • 对于所有数据,n≤2000n\le2000,k≤10k\le10,mod≤109+7\mathrm{mod}\le10^9+7。

三个样例应分别独立运行,每次只输入一组数据。