CCA的树
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

创造是人的天性，更进一步地说，创造是人的意义。
你想创造一棵树，于是你找来了 n 个结点，把它们拼接在了一起 。
你觉得这棵树太单调了，于是又找来 m 种颜料，用其中的一些给这棵树染色。
你认为一个染色的方案是美的，当且仅当树上存在一条好看的链，好看的链满足以下条件：
1、链的两端结点颜色相同 。
2、链上存在一个端点以外的结点，它的颜色与端点不同 。
许久之后，你已经忘记当时是如何拼接的，又是如何染色的，仅仅记得当时找来了多少结点和多少种颜料。
你想计算出染色方案数的期望，以此追忆当年的创造 。
PS：对于一颗已经确定的树，其染色方案数是确定的，但是一颗 n 个结点的树有很多种形态，染色方案数的期望即为 （所有形态染色方案数之和）/ （形态数）。

输入描述:

一行，两个整数 n , m

输出描述:

一行，一个整数表示染色方案数的期望对 1023694381 取模后的值 。
示例1

输入

复制 
4 2

输出

复制 
8

备注:

n,m <= 10^7
PS:由于这题本来是想出在OI赛制的，所以有着充分且巧妙的部分分，建议做题时紧跟部分分思考（Solution的讲解顺序就是一步步拿到部分分），现给出所有部分分，和其在测试数据中所占比例帮助大家思考 。
对于其中的数据，
对于另外的数据，
对于的数据，
对于的数据，
对于的数据，
对于的数据，
对于的数据，