← 返回题目列表

AtCoder · abc378_g

G. 永恒的盖子

中文机器翻译题面 查看原题

分数: 650 点

问题陈述

给你整数 A, B,和 M.

有多少种排列 P = (P_1, \dots, P_{AB-1}) of (1, 2, \ldots, AB - 1) 满足以下所有条件?求计数模数 M.

  • 的最长递增子序列的长度 P is A.
  • 的最长递减子序列的长度 P is B.
  • 存在一个整数 n 这样附加 n + 0.5 到年底 P 不改变最长递增子序列和最长递减子序列的长度。

约束

  • 所有输入值均为整数。
  • 2 \leq A, B
  • AB \leq 120
  • 10^8 \leq M \leq 10^9
  • M 是素数。

输入

输入由标准输入按以下格式给出:

A B M

输出

打印满足条件的排列数,模 M.


示例输入 1

3 2 998244353

示例输出 1

10

例如, P = (2, 4, 5, 1, 3) 满足条件。这可以通过以下方式确认:

  • 的最长递增子序列的长度 P is 3.
  • 的最长递减子序列的长度 P is 2.
  • 对于 n = 4,最长递增和递减子序列的长度 (2, 4, 5, 1, 3, 4.5) 是 3 和 2。

有 10 的排列 (1, 2, 3, 4, 5) 满足条件。


示例输入 2

10 12 924844033

示例输出 2

623378361

打印计数模数 M.