Rezolvare PBinfo #4579

Cerința

Se consideră o mulţime A cu n elemente (distincte).
Determinaţi numărul de posibilităţi de a scrie pe A ca reuniune de m mulţimi. Două moduri de scriere B1 U B2 U ... U Bm şi C1 U C2 U ... U Cm diferă dacă există cel puţin un indice i din mulțimea {1,2 … m} astfel încât mulţimile Bi şi Ci diferă prin cel puţin un element.

Date de intrare

Fişierul de intrare descompunere_prin_reuniune.in conţine pe prima linie doua numere naturale separate printr-un spaţiu n m, cu semnificaţia din enunţ.

Date de ieșire

Fişierul de iesire descompunere_prin_reuniune.out va conţine o singură linie pe care va fi scris numărul reprezentând valoarea cerută modulo 2011.

Restricții și precizări

• 1 ≤ n, m ≤ 1000000000
• Pentru 20% din punctaj 1 <= n, m <= 8

Exemplu:

descompunere_prin_reuniune.in

2 2

descompunere_prin_reuniune.out

9

Explicație

Cele 9 posibilităţi de descompunere a mulţimii {1,2} în doua mulţimi conform enunţului sunt:
{1}U{1,2}, {1}U{2}, {2}U{1,2}, {2}U{1}, {1,2}U{1}, {1,2}U{2}, {1,2}U{1,2}, {1,2}U∅, ∅U{1,2}