hipersimetrie

O matrice hipersimetrică este o matrice pătratică definită recursiv astfel

1. Matricele de dimensiune 1×1 sunt hipersimetrice.
2. O matrice de dimensiune N×N (N>1) este hipersimetrică, dacă îndeplinește simultan următoarele două condiții:

• Este simetrică vertical, orizontal, față de diagonala principală și față de diagonala secundară.
• Submatricele de dimensiuni N/2×N/2 (cu N/2 rotunjit în jos) situate în cele patru colțuri ale matricei sunt la rândul lor hipersimetrice.

O matrice binară este o matrice ale cărei elemente sunt 0 sau 1. Valoarea unei matrice binare hipersimetrice este numărul în baza 2 cu $N^2$ biți obținut prin concatenarea elementelor din matrice citite pe linii de la stânga la dreapta, de sus în jos.

Cerinţă

Cunoscând N și K, să se calculeze a K-a valoare în ordine crescătoare dintre toate valorile matricelor binare hipersimetrice de dimensiune N×N.

Date de intrare

Fișierul de intrare hipersimetrie.in conține pe prima linie numărul N. A doua linie conține un şir de caractere 0 sau 1 reprezentând valoarea lui K în baza 2 (se garantează că primul caracter al șirului este 1).

Date de ieşire

În fișierul de ieșire hipersimetrie.out afișați a K-a valoare în ordine crescătoare dintre toate valorile matricelor binare hipersimetrice de dimensiune N×N. Deoarece această valoare poate fi foarte mare, se cere să afișați doar restul modulo 1.000.000.007 al acesteia.

Restricții

• 1 ≤ N ≤ 1.000.000.000;
• $1 ≤ K ≤ 2^{1.000.000}$;
• Se garantează că pentru valoarea N dată există cel puțin K matrice binare hipersimetrice;
• Pentru teste în valoare de 27 puncte se garantează că N ≤ 1.500
• Pentru alte teste în valoare de 62 puncte se garantează că N ≤ 1.000.000
• Pentru alte teste în valoare de 11 puncte N ≤ 1.000.000.000

Exemplu

hipersimetrie.in

3
100

hipersimetrie.out

186

Explicații

$K=100_2=4$.
A 4-a matrice în ordinea crescătoare a valorii este
0 1 0
1 1 1
0 1 0

Valoarea sa este 010111010 în baza 2, adică 186 în baza 10.