Problem D
Trevliga tal

Det svenska juniorlandslaget i programmering älskar att ha det trevligt när de är ute och reser. En som uppskattade trevlighet mer än någon annan var Mårten. Han hade dock inte samma bild av trevlighet som alla andra. För Mårten hade trevlighet en rent matematisk definition: Ett visst tal är trevligt om och endast om det är delbart med 3.

Eftersom inte alla tal är trevliga så måste man förstås hitta sätt att göra dem trevliga på. Du kommer att få ett heltal, och ditt uppdrag är att hjälpa Mårten räkna ut på hur många sätt han kan göra talet trevligt genom att stryka vissa av siffrorna i talet. Han får dock inte stryka alla siffrorna och det resulterande talet får inte ha inledande nollor (dock anses talet $0$ vara trevligt, så en ensam nolla är okej). Kom ihåg att ett tal är delbart med tre om och endast om dess siffersumma är delbar med tre.

Indata

På den första och enda raden i indata står ett heltal (med upp till $100\, 000$ siffror). Talet innehåller endast siffror $0-9$. Talet börjar inte med en nolla.

Utdata

Ditt program ska skriva ut ett enda tal på en rad: antalet olika sätt på vilket Mårten kan ta bort siffror ur talet så att det blir delbart med 3. Två sätt anses vara olika om indexen där siffror tagits bort skiljer sig. Eftersom svaret kan bli jättestort så ska du slänga bort allt utom de nio sista siffrorna av svaret. Med andra ord ska du skriva ut resten som uppstår då svaret divideras med en miljard.

Exempel

I det första exempeltestfallet kan Mårten åstadkomma delbarhet på ett sätt, genom att stryka ettan i talet. Kvar blir då bara talet 3, som förstås är delbart med tre.

I det andra exempeltestfallet åstadkommer Mårten delbarhet genom att inte stryka någon siffra alls.

I det tredje exempeltestfallet går det inte att skapa ett trevligt tal oavsett vad Mårten gör.

I det fjärde exempeltestfallet går det att skapa de trevliga talen 9, 192, 912 och 12, men det sistnämnda kan åstadkommas på två sätt: genom att stryka de två första siffrorna eller genom att stryka de två mittersta siffrorna.

I det femte exempeltestfallet går det att skapa de trevliga talen 0, 3, 12, 102, 123 och 1023.

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

• För 20 poäng gäller att talet är max 6 siffror långt, och du behöver inte bry dig om att slänga bort hela miljarder (svaret kommer vara mindre än så).

• För ytterligare 20 poäng gäller att talet är max 20 siffror långt, och du behöver inte bry dig om att slänga bort hela miljarder (svaret kommer vara mindre än så).

• För ytterligare 20 poäng gäller att talet är max 1000 siffror långt.

13

1

9

1

1

0

1912

5

1023

6

8702004673

294