Hussein and the gifts#12310

Hussein and the gifts (Çözgüdiň düşündirişi)

Represent a packing as an $n \times m$ binary matrix: rows are gift types, columns are boxes, and cell $(i, j) = 1$ iff box $j$ contains gift type $i$ .

Then no box contains more than one gift of the same type is automatic, and each type must appear in at least one box means no row is all zeros.

Columns have no restriction since boxes may be empty.

For a fixed type (a row), we choose any non-empty subset of the $m$ boxes, giving $2^{m} - 1$ 2^m-1 choices. Rows are independent, so the answer is

(2^{m} - 1)^{n} mod (1 0^{9} + 7) .

(2^m-1)^n \bmod (10^9+7).

MOD = 10**9 + 7

n, m = map(int, input().split())
x = (pow(2, m, MOD) - 1) % MOD
print(pow(x, n, MOD))