問題一覧 > 通常問題

No.1181 Product Sum for All Subsets

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 103
作問者 : PCTprobabilityPCTprobability / テスター : leafirbyleafirby
12 ProblemId : 4752 / 出題時の順位表
問題文最終更新日: 2020-08-22 00:07:13

問題文

(21:24 問題文を更新しました.)
$1$以上$K$以下の整数からなる要素数$N$の数列$S$を考えます.
そのような数列$S$と,集合$\{1,2,...N\}$の真部分集合$T$の組み合わせとして考えられるものは$K^N \times (2^N-1)$通りありますが,そのすべてに対する$\displaystyle \prod_{i \in T}S_i$の和を求めてください.
ただし,答えが非常に大きくなる場合があるので答えを$10^9+7$で割ったあまりを出力してください.
また,空集合の全要素の積は$1$とします.

入力

$N\ K$

$1 \le N \le 2×10^5$
$1 \le K \le 10^{18}$
入力は全て整数

出力

最後に改行してください。

サンプル

サンプル1
入力
2 2
出力
16

便箋上,$G$を,$S_i({i\in T})$からなる集合とします.
$S=\{1,1\}$のとき,$G$として考えられるものは,$\{1\},\{1\},\{\}$の$3$つがあり,それぞれ全要素の積は$1,1,1$です.
$S=\{1,2\}$のとき,$G$として考えられるものは,$\{1\},\{2\},\{\}$の$3$つがあり,それぞれ全要素の積は$1,2,1$です.
$S=\{2,1\}$のとき,$G$として考えられるものは,$\{2\},\{1\},\{\}$の$3$つがあり,それぞれ全要素の積は$2,1,1$です.
$S=\{2,2\}$のとき,$G$として考えられるものは,$\{2\},\{2\},\{\}$の$3$つがあり,それぞれ全要素の積は$2,2,1$です.
従って,答えは$3+4+4+5=16$です.

サンプル2
入力
4 3
出力
5265

サンプル3
入力
3435 2835
出力
618988899

$10^9+7$で割った余りを出力してください.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。