Statistics

Problem Statement for "StringDecryption"

Problem Statement

TopCoder Security Agency (TSA) has successfully obtained the string encryption scheme used by the enemy to encrypt strings of digits. This encryption scheme can be described as follows:

Each non-empty maximum set of identical consecutive digits in the original string is replaced by an integer followed by a digit. The integer is the number of consecutive digits that are going to be replaced (without leading zeroes) while the digit is the same digit as those which are going to be replaced. For example, "122" will be replaced by "1122".

The procedure above is applied twice, first to the original string, and then to the result of the first application. For example, "122" becomes "1122" after one application, and becomes "2122" after the next application.

Although encryption is easily implemented with this procedure, retrieving the original data is not since there may be multiple original strings encrypted into the same resulting string. For example, "2122" may be the result of the encryption of the following strings: "122", a string consisting of 112 copies of digit '2' and a string consisting of 22222....22222 (211 '2's) copies of digit '2'.

It is conjectured that the enemy transmits some additional data that allows the encrypted string to be uniquely decrypted. However, TSA has no access to this data, so their only chance to decrypt the messages is to check all possible decryptions.

You are given a String[] code. Concatenate all elements of code in the order in which they are given to obtain a single string S. Compute the number of different strings that will be encrypted to S according to the scheme described above. Return this number modulo 1,000,000,009. If there are no such strings, return 0.

Definition

Class:
StringDecryption
Method:
decrypt
Parameters:
String[]
Returns:
int
Method signature:
int decrypt(String[] code)
(be sure your method is public)

Constraints

  • code will contain between 1 and 10 elements, inclusive.
  • Each element of code will contain between 1 and 50 characters, inclusive.
  • Each character in code will be a digit ('0'-'9').

Examples

  1. {"2122"}

    Returns: 3

    The example from the problem statement.

  2. {"012345"}

    Returns: 0

  3. {"123","4056","789"}

    Returns: 1555366

  4. {"12121212121212121212121212121","212121212"}

    Returns: 651799081

  5. {"1"}

    Returns: 0

  6. {"11"}

    Returns: 0

  7. {"111"}

    Returns: 1

  8. {"11111111111111111111111111111111111111111"}

    Returns: 1

  9. {"1","23","456","789","101112","131415","161718"}

    Returns: 344698395

  10. {"101010101010101010101010101010101010101010101"}

    Returns: 1

  11. {"10201020102010201"}

    Returns: 1

  12. {"10101010101010"}

    Returns: 0

  13. {"1011011101000111111010101111"}

    Returns: 810067605

  14. {"1212121212130303030121212130303030"}

    Returns: 509348793

  15. { "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890", "12345678901234567890123456789012345678901234567890" }

    Returns: 642514618

  16. {"01133"}

    Returns: 0

  17. {"5443"}

    Returns: 6

  18. {"123074"}

    Returns: 4

  19. {"1234567895444333"}

    Returns: 528348102

  20. {"111221122"}

    Returns: 126102

  21. {"10000000101"}

    Returns: 1

  22. {"36029876684872327223276091861774662608610223162723", "03488815136338720301059585173865765204966825388127", "28905156607840356770675251838346615448480878517234", "48346801533058114299540857443030369316232988018148", "10266938012137248616925283167856138261491565599857", "63098906296356837907112034583226442670798371015701", "04431120878401385924047425666758653777487585276695", "60451685064284613241730873806124686837402534256835", "74510620643600499901411494702324867762597665590427", "82564618006706585886295436740966342057330943523869"}

    Returns: 882582353

  23. {"22"}

    Returns: 1

  24. {"99"}

    Returns: 1

  25. {"3378899857415043028206786551240","458148537","865946310115949600486","008130228329331","724832844787792952289212005000831016601966","79919743576650","139396611420973","8785530585855","7845250500503116701295278","33891871537740309284779463090913978530935350157"}

    Returns: 9976751

  26. {"78603037505669642358009471670184213","9234470","1503921178254118477992074913264425650505018","4125739530995327134134264013612609839385","41091302883145038181509395224216971389115184","692","6520165072190612475462177661463041189450","6667381771560601551339594728418119163448435","36264761175217523275862258348085662109","76"}

    Returns: 30337376

  27. {"1609927548105711018020","512786806774359182436984247254072535532","6974653596390716288504499675156","09661803","6810794119042447","3261794642352117225235936","8908636","12775037","672761168204043265601915","8"}

    Returns: 199732984

  28. {"9","1724297515919412020234781946145791905823789","830835253","316513016608077753906028968852976764682","20990955085594960698359435","56918374361748023819756981284309585982","54806141868418162121721","422","3960859330938364730097400394749","009341386339463"}

    Returns: 178842718

  29. {"64722279223602640441911529742","372994173028868925178998035170342","0800580134987525505687474759476050177428","14905322326778893229507","9209","54406774247865007008009255661597","39384067417701480587760748","7544","7235281722565601763426096756556031725361","035352454401502120986849230304"}

    Returns: 952588584

  30. {"9"}

    Returns: 0

  31. {"65"}

    Returns: 1

  32. {"1475"}

    Returns: 2

  33. {"59155963"}

    Returns: 73045

  34. {"9322476324492855"}

    Returns: 396873888

  35. {"62738563772962467633438136097367"}

    Returns: 980096260

  36. {"12936685163006073891500009174565642612034904646547","55646160570164"}

    Returns: 687148218

  37. {"22225325777231090067273088557049645586223820994059","42662189677996100833411816280786748696276640110740","1703811693603376226444104955"}

    Returns: 545349315

  38. {"86811008128382336444074599791994663150749518710142","47222578472938115479431366687324668307465538082338","42195558086498255373594244947575895249800602768247","89244304476706635780908512975108819570600477064869","01697778404639561879975113210491793244567668804730","604306"}

    Returns: 525880940

  39. {"83416165878880449247216664759065649174593338718783","98164119571673001214963177270080118022631585412208","37279778838492860051884672757514107485297268172430","75960462890344156877358159664885156205832364440656","32530658446760466482925463938027844060067201841767","97785977154263549999134121102764465428953699847125","11558791062072196530867657766951948688827108902725","84809326645526408326519851317006813462767623878614","79889750422099024008466772917629431677460295455162","89169616446781735292975868416537309611466048846443"}

    Returns: 326870122

  40. {"1101"}

    Returns: 1

  41. {"2201"}

    Returns: 1

  42. {"8739"}

    Returns: 9

  43. {"4608"}

    Returns: 1

  44. {"5919"}

    Returns: 1

  45. {"5559"}

    Returns: 6

  46. {"3622"}

    Returns: 4

  47. {"9002"}

    Returns: 1

  48. {"1769"}

    Returns: 2

  49. {"1111"}

    Returns: 1

  50. {"7007"}

    Returns: 1

  51. {"9999"}

    Returns: 1

  52. {"1111"}

    Returns: 1

  53. {"9009"}

    Returns: 1

  54. {"3977"}

    Returns: 4

  55. {"10101"}

    Returns: 1

  56. {"11121"}

    Returns: 1

  57. {"93872"}

    Returns: 103

  58. {"80086"}

    Returns: 1

  59. {"19991"}

    Returns: 21

  60. {"95595"}

    Returns: 1

  61. {"40206"}

    Returns: 1

  62. {"93007"}

    Returns: 1

  63. {"59157"}

    Returns: 65

  64. {"11111"}

    Returns: 1

  65. {"77707"}

    Returns: 1

  66. {"99999"}

    Returns: 1

  67. {"11111"}

    Returns: 1

  68. {"90099"}

    Returns: 1

  69. {"77739"}

    Returns: 85

  70. {"1101000001"}

    Returns: 1

  71. {"1002001222"}

    Returns: 100201

  72. {"7883445291"}

    Returns: 11125337

  73. {"6044608202"}

    Returns: 670951

  74. {"1517757753"}

    Returns: 1975784

  75. {"5599955595"}

    Returns: 6754

  76. {"2700400708"}

    Returns: 1

  77. {"2300700303"}

    Returns: 1

  78. {"8721324912"}

    Returns: 10759064

  79. {"1111111181"}

    Returns: 1

  80. {"7707707007"}

    Returns: 771

  81. {"9999999999"}

    Returns: 1

  82. {"1111111111"}

    Returns: 1

  83. {"9990090009"}

    Returns: 10

  84. {"9799977733"}

    Returns: 14034705

  85. {"10100100011001010000010010100000111100110100110000","01101110101110111110001110010011001000010001100110","01111110010001010011101101010101000011111110000110","01111111001011001111101011011010100101010001000100","10010101110111010110001001001111011111000001001111","00110000111000011111100010100010001111101010110100","11100011110011100100111100100000011001100100100110","11100010000101000001001111101101101110101010000110","10000011010111000111001011111010010100110110010001","11011010101001101001001100011001011010010110111101"}

    Returns: 67927623

  86. {"11111111111111111111111111111111111111111111111111", "12222222222222211122222222222221112222222222222111", "12000000000000211120000000000021112000000000002111", "12222220222222211120222222222221112022222222202111", "11111120211111111120222222222221112022222222202111", "11111120211111111120000000000021112000000000002111", "11111120211111111122222222222021112022222222202111", "11111120211111111122222222222021112021111111202111", "11111120211111111120000000000021112021111111202111", "11111122211111111122222222222221112221111111222111"}

    Returns: 371459312

  87. {"41685274313827535453798656756873999278782182853862","44275629277299438578439925811693571496157166177757","25861569782747825685923416236779731491352975947535","23624658436947735227594428992659635363435852857542","71834131668359193728591662668862379185734981818551","81688666897569449445382215539682273442159591941742","31955463425384587713241973889459361641887685176271","59699989992781629395693526979918943926975466132291","46733916686389399241168894132852852141776262795896","19278883264589128743116938943555145865741323141585"}

    Returns: 642493661

  88. {"66062888060800064606064844468026206020406044600086","84280468620082864806804666462624282880866062446888","68622460420424484668400226646040406082808606642620","86684006004866868046828002884604242486880660848488","46446826220440604040840602826266042422408000006808","28082004820840042460246208080240628646480864664886","60280022202004064684042820428068264204808642284248","08260204404404882624024080668802864486008602206826","22084606880466060222624420086480062220068424866042","24806448880264046882044844662662646040486240866086"}

    Returns: 147074756

  89. {"35935559991737115373591731357111595317375977575571","57133159531399995111793117777139791175335193551595","59511719195313753913151955573777153195957313713359","97519571111337373511775111999971739339597971579939","53557939973577977915731193933193375371753735591139","53337519555195171751953157155311177173135519733777","53175175357531393157719571195575719517375919111571","13171139311953153179397913397337599171517713959391","75975153979779335139779375113393133339133775911971","37397159139339971191775975759179537577959597799179"}

    Returns: 469048629

  90. {"99955555959959995559999555559559559559995999555555","59595555995999995599595999559559599555555959959595","95959955599995599959599555595555599555559955999599","95995555959995559559999595595999559599555599995599","95955959959599595995955595999599959599959995995595","59555995955955995599559995955955955595959599559559","95595959959959955999955959555955959555595999559995","99999995595959955955995599595555955959595959599599","95555595995559955595599995599555955595999999955959","55999999995599995559599599595555595559555559955599"}

    Returns: 818129029

  91. {"53000944450636270000996070002080066710260050885106","00000005070005350310939900670000705035837000050898","06620307207400430000096010080800180702000032050000","70705052900716046950528060000005075001000504320000","12820380649659005530210780012002955904525420030200","60015110592487040272720070900010045009970006332480","01403013260860750078092004026080101010522000008006","73000544053005846040737123687100805800004019429535","58005690404880009157000000100440024030020390200084","00403630935830004099800000076000000706809000500001"}

    Returns: 641965880

  92. {"10000000400900000000000400000100002005000000006010","09408008006009020003080090040990000103000090000000","00000097000060060050002000090545007000250005087800","00070000000000670760106410009008009200300050323000","00003000027080020104060260200000004100202006660500","00047906070700008000390200070000744009098008000025","00206076000000080822000000070050508905800004000296","10806080020700004303070002845000010000000000631208","00007090008500005900900500500600000010813008000500","50000880051177800000001280000035000000000007207091"}

    Returns: 292770134

  93. {"99371524225345064162523985388289539156544645286574","53088275981113826399555137675766343512896841251275","21201838922779092274291823416242266783236994653782","24215240184832834712381573019292429949592271289225","83784589821651253721630572968150288115429267584955","90272308118206782626365825114161705394923858399296","65254814967476405574382273225345322669488849055234","28487110991277198932783264178386692472868524747616","95241443377762024361284637461394747571624548824840","94876037969899922288374961134446234297388616809782"}

    Returns: 925291818

  94. {"21111111111171114111112211101111011111164111111121","11112153919111514111161111111441111111111111412158","11171111111113951411311211114111113212151111111111","11111111111111111111211111111117100112111111611111","11131111418110161111341149111111111111116111310111","11181111111214111113111019111815111111151151111111","11111110111111409115111318111311151111111111111111","11198111161117131195111111111111111111111111112111","11136191111111318711111111111111111111161111121116","11111211931141111119111111171111111111111111111111"}

    Returns: 998585010

  95. {"70707777000707077700777077070700700077000070777707","77070777077770070007707777707770070077707007077000","07077770700070777070000000770007000770700707077000","00007700707777000070707007707770000077077700707707","07707770707077070007070077770077007707770770777770","77070000000700700707077700077077070070070707700700","07007770777707070077700000070707077007000770707007","77707007077700770077007070000000707700007777700000","77070707700007077070777707077000700700007000000777","70070070077707707777700077070077707777777000070007"}

    Returns: 264383774

  96. {"99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999"}

    Returns: 1

  97. {"11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}

    Returns: 1

  98. {"90900099000000000090009909000000990990990900090900","00900999909090900000990000900090009090900900000999","00000000000009090099999000099090090000090009990999","90900099909090099090000000090090009090009090099090","09090000900000009000009900009909990000009009000900","00000909009990000999000900000900900000000090009900","90000900000000000009009009009999990990099900000900","09909000000900900090099000090909099990000000009009","00009099900009090900090000090000099000900090090000","00009000000999999900000099009990999000099000000009"}

    Returns: 190038846

  99. {"93339797333737973797999339977339379373979933333777","79797797977779979399793933999379393379937379773793","33373793979937979333999997733779337799973939737793","39739977793799939977337799993977739937337779797377","39933379799339979333379379997797973377333377399937","79393939399793797939799797793397937779993397379997","93933999979373933977333979799397979733379393337999","37999393333739977999737379999773777939393993797937","97939979397973773733977739973977933377997333373933","99777979939777733333739333937737797777933777797393"}

    Returns: 327626533

  100. {"11101110011110011001101000111101110011111010011100","11111110011010111000000010001000101001111100001001","00011111011100100001111010000110001101010101111101","10010101110011111010000010010100010001001101010001","00111110001010110011010000011010111110000000100111","00010110101000100001000010111101011010111010000101","11000110001110100110111110001100111000111100001101","11111011101111000110000000110010001110000101000010","01111100000010110100111101000101110001100111101011","01110110110111101010101000111001101011001000101111"}

    Returns: 612713306

  101. {"10121012200022021000100000100210022011222012022211","20201001122120001212020000022111122100122222102111","22121122000011100121021221001021200000001222200021","02012100001210101021200000011111012020201022211020","11022021211021221220022010110220020101112210012002","21221221002101222010010212211010112201100111001101","01110111202001101202221020121022112201201010210121","21111211021101220202212022201221121112210010010120","02211222021101020100111102101210110202221021211211","12210002011220211102102220211102111212111120211211"}

    Returns: 465500600

  102. {"65671629774182427156574887934193312994746555553497","76847997955974253526919159976478199563956667543566","84653664814768322288899836734482297191921162617266","65961149755415271339665636527399432514653869262332","33584755177136234325981746689469677495376618628798","98732677119479124429794951513915928325392464575349","94876325829917893175294999795843318794825532722397","13133729379831985481324837979221325948716144528369","37892677377375536815242773399281666519334599528889","77154754687798272426213212221454525194814761337532"}

    Returns: 10402103

  103. {"26828802408200260404046888206824880606064024082048","02640000420848068686860266022004866086244848484448","88402664426466268440688286262044086286204046488864","24202008280800860802264244024064826080824444668208","84006846246242260428804008068222068600286882008286","66004244284264404262864604846846200442268266662864","86228408066282284800448688060608080686004024026604","86046000608020264660428624244820048046400268864008","40606428026266202244406640820048000804204846866440","46084260084644202806424044480086248642880000084844"}

    Returns: 221898049

  104. {"95939591193575135315757315757537375513911511393393","15939571399139335139739333995555199775539133577397","71979333355153373153115535337395357335997717319131","53593717591955977757575975571117377737791959971311","95513535513719353597199711935175751535557359979735","79377111559755179333191135913979153355799311753939","77577971931935979353795599993737553931517739951959","73599397515719533517537177719157173151533995793979","57177315977117513313337937713395137519755355713715","79735337993793117533135379373933797131559319575353"}

    Returns: 884925764

  105. {"59555955595959999995559955995599555959599999559599","95959595995959555599599559595959559595555595599995","59999955595995995995995959555555595559955595555599","59959559995955599599995599995999595955555995559955","59995559599955999559559959959595999959599595999595","59955595995599559999999999555999555595599595595999","55959999595955959999995555999999559959955999559595","95959999595995559999955955995995955555959595559955","59599599559599595599999955599959599555599955955999","99999999599599599959595995999959555959595999595959"}

    Returns: 268715264

  106. {"20167040008700979000795007071000086394006060038513","30049009000879005900920090860307570303840920214400","00456000084000005050524700600100508154480570002486","80658007072120044704030321004200300800673185730000","00670000904002502060700286480950108020166077050210","00000000800160400000304905930709050078673040510602","90000690110000900680002163000478002030933418014009","77932030502050050060603020005908904511504020000600","90010009160020002236609106097992407323373000930007","67401063899952002193201008086000801800505500870308"}

    Returns: 533985197

  107. {"19000005000020008030000086063200000005000001090250","00608001500700000000000300000100009006000000000010","20000000008204802000600100890030000000960007379000","00001000508608009002015800300900100180900700700000","13000000037000000000000500840030000067000000000606","08400000000008400090000000030109600700000200904624","00894000000000080000420600700013007001000000000000","50110000000708050206040030009600000000500009008600","00900000005809500060010002000000003000292066000005","96089400020000104702800000100000600901000004340564"}

    Returns: 639677630

  108. {"45683465141775737968483719429645214875412354594619","47785799336579394982125117511748418793185291597733","71226722266722707802657995414535234863739677562301","35757492568651209893088837817182839428826151972387","73363128143297956872754439083427127265713668343173","12858342417565177475536383844392511698776595966980","39321677431897825899655496159835773367845976265268","45898351810729911493964072744951992199425647524386","03149683554477653956466796296856576632227294322954","42798771374973728487876634908231963646672679052806"}

    Returns: 387368985

  109. {"31411111511112211411111211111944111119118141211115","11211111111111111111111111711111161211141111115111","36111111102111151111741111111111116111111118112211","11121611111111111911111111111111111111111111111111","16111011110111111811111111116111111111111761111982","11111751191181111113111111111101111511111111110111","55111015111111111116111176111111111111111111511111","13121186111111111711411111411111183111411311116111","11111015110111111117711181111111180111181111311111","11121111111111111151111128141119111911111381751111"}

    Returns: 35610697

  110. {"77770070707700007770770777700700770007770707070707","07707777007000077077777700070770070777000707070000","00700770700007770700707077707077007070077770000700","00077770700007777007777777070000077007707700070077","70007007700707077077700770007770777770000770007770","77777770700070770707000770707077070700070077700070","77777070000777777007007077770007077070077077007777","07070000770070070077077007007707777000077007707077","70070000700700000000070707700077770077777077077070","00700007077707077777700777700707707770077770777777"}

    Returns: 893545204

  111. {"99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999"}

    Returns: 1

  112. {"11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}

    Returns: 1

  113. {"99090900000090000090990090000000090009000000090000","09990900900009009000009000900000909000009999900000","00990009090099900999000000990009900000009090000090","00900000000000000900900009009900000090009099090099","00000000000009009900000009909090009009000009000090","09009090900900900990009900900090990099900099000000","00000009999909900090900000000000090000000009909000","90990900000000000909090000090900009009900000009009","00000990909090900099000909900999990099000990000000","90000009090009000000009090009900090099090990900009"}

    Returns: 261131716

  114. {"73339399777793977977993977379337337393333379379339","99973779773797937779793393999773779777997333799999","99799337793939933979777779979797377937999773799393","93339339797737399979397933333399377973339939797979","77939773777379777333739997973397933799939793737737","79779733973339333799733979979777737733339797933399","77399333779777939393977333993973737793939999379993","37333939937999397739733993997373337973797397333373","99793993737373997939737799999977737397939999799973","79377993337777399979799933973377799379373373939799"}

    Returns: 403084810

  115. {"099"}

    Returns: 0

  116. {"990"}

    Returns: 0

  117. {"059"}

    Returns: 0

  118. {"390"}

    Returns: 0

  119. {"000"}

    Returns: 0

  120. {"000"}

    Returns: 0

  121. {"011"}

    Returns: 0

  122. {"010"}

    Returns: 0

  123. {"00999"}

    Returns: 0

  124. {"90900"}

    Returns: 0

  125. {"01720"}

    Returns: 0

  126. {"89210"}

    Returns: 95

  127. {"02020"}

    Returns: 0

  128. {"00000"}

    Returns: 0

  129. {"01111"}

    Returns: 0

  130. {"01000"}

    Returns: 0

  131. {"09099900009000090900099909990999090990900000099909","09099999009900900999090000990099099000099000909090","99090900990000000099909000000000909999099090990900","99909990990099099000000009009999990999099909090099","09090099900990009099990909909090099999090099909909","00099090900099099000099000909900900990099990090999","90000999909000009900009090990090990099990990009909","99990090009000999990090009099909009009999090099999","09990009000090009999099090909909099990090009900099","00990999099009900909009000990000900099000999900990"}

    Returns: 0

  132. {"09900090909090090900090009000099099909099900909000","99090000090999009999990099999900990009990009900000","09909909099909909009099900099090909999999909009900","90990000900000909009009900900909009990900090999999","90999900999009990999090990090900090000900990090099","99909090900990009090000000900009099090090999009900","90999009009909999900900909090990090990909090999099","00000909090909909099090000099099909000009009900000","09009990009909900909000000900909990909990099990900","09090909909990990099090999009009090099990099909090"}

    Returns: 0

  133. {"05203936921287538777962710202332719110928991255759","36690858274524546049434610672235698693937248157619","59097434386887655934216575277827905197973230273138","47409000513286337029909518467500259812668543538485","76563304554349151179323361481271529475752789351942","93078034727057383919691156200492115581741486722397","55852672116357986911906560243212853064213449523551","32455120086003211418424874837795741689196682591172","87570853177243586347436294474014308050368956460564","14797949659568463389172408504255848399155932496788"}

    Returns: 0

  134. {"73204937210511209436040421709948897285994818092217","42760559051634767928651321726221469364974639119246","34333360246296581589618909998989753775448136069920","69349002198319896645962110965099782175473727642764","12539529903814198049571673662858374771334267929649","80903856121922362740880444132442777821168490833591","01654877957325152245495501127396475894486465906614","24200868272412199797308772962235037824484269524319","92458060339361658128059841731311812136793840235729","58382454021684578855470119709362097136727465022310"}

    Returns: 870956612

  135. {"00860900350001019800200097003002108067110000800060","00760801300000170565004700638520240030860070000000","03018010000712640500095803303800000200060005902200","50450098000000330190405000210007006870080007070805","45800000693001730080000500069600008020080000050003","05015400000007600020060910729201080005090030600008","60903210400090008005070005703000200200000506320064","90002040010040625510000030900640006000000016000900","82048060001010009407009000700004030670040040070382","00000017740000670009505000000050490000027002800700"}

    Returns: 0

  136. {"50094000105407050800057080300801020000092010810600","04073021010950880600004840050087000000240850030004","40062270926100060860000000820800050031056070320034","08000507070020000690000002040300780609000095000054","02650020070007000001004200369000600309000330603010","00000006640000400009096304002410071600079200004700","09004049905090800000020190000030090000079050000000","00302007003035010032500000100005000000800005204080","93004702000000401940702000706080000040008040000607","00600090905100606400000017054000090004070090030800"}

    Returns: 772976177

  137. {"01001011110111101010110111111111111011101111111110","11101001111111111110110100101111011010111111110111","11110111111101110101111111001111101111010111111011","01111111111011011111110100110100111111110011110011","10110101010100101111100111111010111111110011111000","11010110111111001111111110100111111111111011111111","10101111101101110011111111101011110111110111111101","11111110111111111111111011101111111111111111111011","11110111011110111011111011111011111111101111110111","01111001110111110011111101011011111011111010111111"}

    Returns: 0

  138. {"11101011111011111111111101111111101100111111111111","11111111101111111111101111111101111111110011111111","11101111011110111011111101111111111101011011111111","11100111111011111111001111101101011101011111111011","11111111101111111111101101111100011111111011101011","11110110111111010011110111111101111100011110111010","11111101110011101101101111011111110101011011111101","11101011111100111011111100010111111011001111011010","01010101100111111111111111011111110110111011111111","11110001110111101110101101011110011111101101111110"}

    Returns: 57237018

  139. {"000"}

    Returns: 0

  140. {"111"}

    Returns: 1

  141. {"222"}

    Returns: 1

  142. {"999"}

    Returns: 1

  143. {"00000"}

    Returns: 0

  144. {"11111"}

    Returns: 1

  145. {"22222"}

    Returns: 1

  146. {"99999"}

    Returns: 1

  147. {"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}

    Returns: 0

  148. {"11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}

    Returns: 1

  149. {"22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222","22222222222222222222222222222222222222222222222222"}

    Returns: 1

  150. {"99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999"}

    Returns: 1

  151. {"9012345678"}

    Returns: 11642771

  152. {"90123456789012345678"}

    Returns: 235581760

  153. {"90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678","90123456789012345678901234567890123456789012345678"}

    Returns: 898509610

  154. {"9876543201"}

    Returns: 1365956

  155. {"98765432019876543201"}

    Returns: 791126442

  156. {"98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201","98765432019876543201987654320198765432019876543201"}

    Returns: 919631980

  157. {"123456789"}

    Returns: 164386

  158. {"123456789123456789"}

    Returns: 931359858

  159. {"12345678912345678912345678912345678912345678912345","67891234567891234567891234567891234567891234567891","23456789123456789123456789123456789123456789123456","78912345678912345678912345678912345678912345678912","34567891234567891234567891234567891234567891234567","89123456789123456789123456789123456789123456789123","45678912345678912345678912345678912345678912345678","91234567891234567891234567891234567891234567891234","56789123456789123456789123456789123456789123456789"}

    Returns: 294806111

  160. {"12345678912345678912345678912345678912345678912345","67891234567891234567891234567891234567891234567891","23456789123456789123456789123456789123456789123456","78912345678912345678912345678912345678912345678912","34567891234567891234567891234567891234567891234567","89123456789123456789123456789123456789123456789123","45678912345678912345678912345678912345678912345678","91234567891234567891234567891234567891234567891234","56789123456789123456789123456789123456789123456789","123456789123456789123456789123456789123456789"}

    Returns: 956318749

  161. {"987654321"}

    Returns: 1365956

  162. {"987654321987654321"}

    Returns: 702989870

  163. {"98765432198765432198765432198765432198765432198765","43219876543219876543219876543219876543219876543219","87654321987654321987654321987654321987654321987654","32198765432198765432198765432198765432198765432198","76543219876543219876543219876543219876543219876543","21987654321987654321987654321987654321987654321987","65432198765432198765432198765432198765432198765432","19876543219876543219876543219876543219876543219876","54321987654321987654321987654321987654321987654321"}

    Returns: 243789252

  164. {"98765432198765432198765432198765432198765432198765","43219876543219876543219876543219876543219876543219","87654321987654321987654321987654321987654321987654","32198765432198765432198765432198765432198765432198","76543219876543219876543219876543219876543219876543","21987654321987654321987654321987654321987654321987","65432198765432198765432198765432198765432198765432","19876543219876543219876543219876543219876543219876","54321987654321987654321987654321987654321987654321","987654321987654321987654321987654321987654321"}

    Returns: 96151084

  165. {"12"}

    Returns: 0

  166. {"1212"}

    Returns: 1

  167. {"12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212"}

    Returns: 816032395

  168. {"12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","1212121212"}

    Returns: 998659543

  169. {"12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212","12121212121212121212121212121212121212121212121212"}

    Returns: 540121445

  170. {"10"}

    Returns: 0

  171. {"1010"}

    Returns: 0

  172. {"10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010"}

    Returns: 0

  173. {"10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","1010101010"}

    Returns: 0

  174. {"10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010","10101010101010101010101010101010101010101010101010"}

    Returns: 0

  175. {"90"}

    Returns: 0

  176. {"9090"}

    Returns: 0

  177. {"90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090"}

    Returns: 0

  178. {"90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","9090909090"}

    Returns: 0

  179. {"90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090","90909090909090909090909090909090909090909090909090"}

    Returns: 0

  180. {"92"}

    Returns: 1

  181. {"9292"}

    Returns: 1

  182. {"92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292"}

    Returns: 161351189

  183. {"92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","9292929292"}

    Returns: 639594191

  184. {"92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292","92929292929292929292929292929292929292929292929292"}

    Returns: 686832720

  185. {"102"}

    Returns: 1

  186. {"102102"}

    Returns: 1

  187. {"10210210210210210210210210210210210210210210210210","21021021021021021021021021021021021021021021021021","02102102102102102102102102102102102102102102102102"}

    Returns: 105694957

  188. {"10210210210210210210210210210210210210210210210210","21021021021021021021021021021021021021021021021021","02102102102102102102102102102102102102102102102102","102102102102102"}

    Returns: 368836106

  189. {"303"}

    Returns: 1

  190. {"303303"}

    Returns: 1

  191. {"30330330330330330330330330330330330330330330330330","33033033033033033033033033033033033033033033033033","03303303303303303303303303303303303303303303303303"}

    Returns: 910552009

  192. {"30330330330330330330330330330330330330330330330330","33033033033033033033033033033033033033033033033033","03303303303303303303303303303303303303303303303303","303303303303303"}

    Returns: 982335126

  193. {"10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 1

  194. {"90000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000009"}

    Returns: 1

  195. {"10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000200000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 1

  196. {"10300000000000000000000005000000000000000000000000", "00000000000400000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 1

  197. {"60303030901060805080509010907030805040305020308060","80401050705020201090504030504080401010409020808020","10303040609080702020604010308050308070908080107050","30801070203070707070106010208060903080606010505030","50805080308020308060609070906040402050806080607050","20107090901030603070603060105050602090701080408040","40304070809060402090705090601070205090108010605050","60703080406030906030609020406060506050709080503090","60802090502030603070702090205060609090209030908030","3090901070702070703030307060906060907010107020803"}

    Returns: 1

  198. {"60303030901060805080509010907030805040305020308060","80401050705020201090504030504080401010409020808020","10303040609080702020604010308050308070908080107050","30801070203070707070106010208060903080606010505030","50805080308020308060609070906040402050806080607050","20107090901030603070603060105050602090701080408040","40304070809060402090705090601070205090108010605050","60703080406030906030609020406060506050709080503090","60802090502030603070702090205060609090209030908030","30909010707020707030303070609060609070101070208030"}

    Returns: 0

  199. {"0303030901060805080509010907030805040305020308060","80401050705020201090504030504080401010409020808020","10303040609080702020604010308050308070908080107050","30801070203070707070106010208060903080606010505030","50805080308020308060609070906040402050806080607050","20107090901030603070603060105050602090701080408040","40304070809060402090705090601070205090108010605050","60703080406030906030609020406060506050709080503090","60802090502030603070702090205060609090209030908030","3090901070702070703030307060906060907010107020803"}

    Returns: 0

  200. {"60303030901060805080509010907030805040305020308060","80401050705020201090504030504080401010409020808020","10303040609080702020604010308050308070908080107050","30801070203070707070106010208060903080606010505030","50805080308020308060609070906040402050806080607050","20107090901030603070603060105050602090701080408040","40304070809060402090705090601070205090108010605050","60703080406030906030609020406060506050709080503090","60802090502030603070702090205060609090209030908030","30909010707020707030303070609060609070101070208030"}

    Returns: 0

  201. {"10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000001100200000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 183331047

  202. {"11000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 1

  203. {"11111000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 1

  204. {"11111000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000011111"}

    Returns: 125

  205. {"10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000111111111111000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 1

  206. {"10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000022222222222222000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    Returns: 45834474

  207. {"22201122221221102021210200121010001011021110211102", "20200120210011220112222212011000222002221012110122", "12210002201211222011021021202200010121220100102200", "02120111022222120201012212210111222021012121012110", "12212112102010110121201112220111121100102200102211", "11011102201011200220201011100010221220121002201222", "00101021200012000012001002210222002112012122202001", "22200022112200202000200112000102211022110102111021", "00011112000221002021001002000220120002222021121100", "10010021110010010110210202211220220210012102002111"}

    Returns: 191043061

  208. {"22"}

    Returns: 1

  209. {"33"}

    Returns: 1

  210. {"43"}

    Returns: 1

  211. {"91"}

    Returns: 1

  212. {"19"}

    Returns: 0

  213. {"11"}

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: