Fișierul intrare/ieșire	bignum.in, bignum.out	Sursă	Science On 2021, clasa 7-8
Autor	Tamio-Vesa Nakajima	Adăugată de	Voicu Mihai Valeriu • bitoneko
Timp de execuție pe test	0.1 sec	Limită de memorie	262144 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Bignum (clasa a 8-a)

Vom nota un număr în baza 2 cu cifrele b[1], ..., b[k] prin b[1]...b[k]₂. De exemplu, 101₂ este numărul 1 + 2² = 5. Definim ordonarea unui număr în baza 2 ca fiind numărul ce rezultă din sortarea în ordine crescătoare a cifrelor numărului. De exemplu, ordonare(101₂) = 011₂ = 1 + 2¹ = 3, sau ordonare(10101₂) = 00111₂ = 1 + 2¹ + 2² = 7.

Se dă un număr N₂ în baza 2. Să se calculeze suma ordonare(1₂)+...+ordonare(N₂) modulo 10⁹ + 7.

Date de intrare

Primul rând al fișierului de intrare conține numărul N₂, în baza 2.

Date de ieșire

Fișierul de ieșire va conține suma descrisă anterior, în baza 10.

Restricții

• Pentru teste în valoare de 20 de puncte, N₂ are cel mult 20 de cifre în baza 2
• Pentru alte teste în valoare de 30 de puncte, N₂ are cel mult 2 000 de cifre în baza 2
• Pentru alte teste în valoare de 50 de puncte, N₂ are cel mult 200 000 de cifre în baza 2

Exemplu

Explicație

Observăm că: ordonare(1₂)+ordonare(10₂)+ordonare(11₂)+ordonare(100₂) = 1₂ + 01₂ + 11₂ + 001₂ = 1 + 1 + 3 + 1 = 6