SPOJ in Armenian

Տրված է տող, որը պարունակում է միայն 0, 1, և ?  սիմվոլներ։ Դիցուք ? սիմվոլների քանակը k է։ Այդ դեպքում դրանք 2^k եղանակով կարելի է փոխարինել 0-ներով և 1-երով և ստանալ 01 (այսինքն միայն զրոներից և մեկերից կազմված) հաջորդականություն։

Յուրաքանչյուր 01 հաջորդականությունը երկու հարևան տարրերի տեղափոխության գործողությունների միջոցով չնվազման կարգով տեսակավորելու համար մինիմալ անհրաժեշտ գործողությունների քանակը անվանենք ինվերսիաների քանակ։ Օրինակ, 10010 հաջորդականությունը տեսակավորելու համար անհրաժեշտ է կատարել չորս գործողություն.

10010 -> 01010 -> 00110 -> 00101 -> 00011

Այսինքն, այս դեպքում ինվերսիաների քանակը 4 է։

Հարկավոր է հաշվել բոլոր 2^k 01 հաջորդականությունների ինվերսիաների քանակների հանրագումարը 1000000007 թվի վրա բաժանելուց մնացորդը։

Մուտքային տվյալներ

Տրված է միայն 0, 1, և ? սիմվոլներից բաղկացած մեկ տող։ Տողի երկարությունը չի գերազանցում 500 000-ը։

Ելքային տվյալներ

Պետք է արտածել մեկ թիվ՝ խնդրում պահանջվող հանրագումարի մնացորդը։

Օրինակ

Մուտք.
?0?

Ելք.
3