禁止动规

题号：NC19836
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你在一个无限长的数轴上，一开始你在原点
本来你只有两种操作：向左dp，以及向右dp
然而由于禁止dp
于是你只能另寻出路
万幸的是，dp之神随机给了你n个变量，既x₁,x₂, ... , x_n，每个变量的值在 $1 \sim m$ 之间，且是整数
每次你可以选择一个变量x_i，然后向左走x_i个单位，或者向右走x_i个单位
问走到原点右侧1单位距离的概率是多大？
既随机给定n个变量后，存在至少一种从数轴上的0点走到1点的方案的概率

设答案为 $\omega$ ，那么你只需要输出 $\omega \times m^n$ 在模2⁶⁴意义下的值

注意：

1. 一个变量可以选多次，也可以不选

2. 可以走到负半轴

输入描述:

第一行两个整数n,m，含义见“题目描述”

输出描述:

一行一个整数表示答案

示例1

输入

复制

10 10

输出

复制

9990174303

备注:

数据范围
1 ≤ n ,m ≤ 10¹¹