Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Educational Codeforces Round 11 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

math

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Different Subsets For All Tuples

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFor a sequence *a* of *n* integers between 1 and *m*, inclusive, denote *f*(*a*) as the number of distinct subsequences of *a* (including the empty subsequence).

You are given two positive integers *n* and *m*. Let *S* be the set of all sequences of length *n* consisting of numbers from 1 to *m*. Compute the sum *f*(*a*) over all *a* in *S* modulo 10^{9} + 7.

Input

The only line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 10^{6}) — the number of elements in arrays and the upper bound for elements.

Output

Print the only integer *c* — the desired sum modulo 10^{9} + 7.

Examples

Input

1 3

Output

6

Input

2 2

Output

14

Input

3 3

Output

174

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/29/2023 04:43:53 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|