{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eJava language contains arrays as special classes. Since every class in Java derives from \u003ccode\u003ejava.lang.Object\u003c/code\u003e, every array does, too. An array of objects can contain other arrays as elements. In this problem, we consider only arrays that contain other arrays as elements, or arrays that are empty.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eSometimes we should print the given array as a string. To do this, we may use the dedicated method, \u003ccode\u003ejava.util.Arrays.deepToString\u003c/code\u003e. This method returns a string representation of the \"deep contents\" of the specified array. If the array contains other arrays as elements, the string representation contains their contents and so on. This method is designed for converting multidimensional arrays to strings.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe string representation consists of a list of the array\u0027s elements, enclosed in square brackets (\"[]\"). Adjacent elements are separated by the characters \",\u0026nbsp;\" (a comma followed by a space). All the elements are converted to strings by invoking this method recursively.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFor example, we may take the array\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par_pre\"\u003e\u003cpre\u003eObject[] A \u003d new Object[2];\r\nA[0] \u003d new Object[0];\r\nA[1] \u003d new Object[0];\u003c/pre\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eand the invocation of \u003ccode\u003edeepToString\u003c/code\u003e on it will return \u003ccode\u003e[[],\u0026nbsp;[]]\u003c/code\u003e.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eNote that a variable of object type in Java is a reference. As a result, an array may contain the same object more than once, and two arrays may contain the same object as an element. So, different arrays may give the same string representation. For example, the array\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par_pre\"\u003e\u003cpre\u003eObject[] B \u003d new Object[2];\r\nB[0] \u003d new Object[0];\r\nB[1] \u003d B[0];\u003c/pre\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003ewill have the same string representation as array \u003ccode\u003eA\u003c/code\u003e has.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eLet\u0027s determine the equality relation for array configurations. Two configurations \u003ccode\u003eA\u003c/code\u003e and \u003ccode\u003eB\u003c/code\u003e are considered equal if the following statements\r\n\u003cul\u003e\r\n \u003cli\u003e\u003ccode\u003eA[a\u003csub\u003e1\u003c/sub\u003e][a\u003csub\u003e2\u003c/sub\u003e]…[a\u003csub\u003ek\u003c/sub\u003e] \u003d\u003d A[b\u003csub\u003e1\u003c/sub\u003e][b\u003csub\u003e2\u003c/sub\u003e]…[b\u003csub\u003ek\u003c/sub\u003e]\u003c/code\u003e\u003c/li\u003e\r\n \u003cli\u003e\u003ccode\u003eB[a\u003csub\u003e1\u003c/sub\u003e][a\u003csub\u003e2\u003c/sub\u003e]…[a\u003csub\u003ek\u003c/sub\u003e] \u003d\u003d B[b\u003csub\u003e1\u003c/sub\u003e][b\u003csub\u003e2\u003c/sub\u003e]…[b\u003csub\u003ek\u003c/sub\u003e]\u003c/code\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n are equivalent for all possible sequences of \u003ccode\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/code\u003e and \u003ccode\u003eb\u003csub\u003ej\u003c/sub\u003e\u003c/code\u003e. Here, the relation \"\u003ccode\u003e\u003d\u003d\u003c/code\u003e\" should be treated as \"equal by reference\".\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eGiven the outcome of the invocation of \u003ccode\u003edeepToString\u003c/code\u003e, find the number of different array configurations that give the specified result. You may assume that the given string will be a string representation of multidimensional array with constant dimensions created with the construction \r\n\u003ccode\u003enew Object[a\u003csub\u003e1\u003c/sub\u003e][a\u003csub\u003e2\u003c/sub\u003e]…[a\u003csub\u003en\u003c/sub\u003e][0]\u003c/code\u003e. Here \u003ci\u003en\u003c/i\u003e ≤ 100; \u003ci\u003ea\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, …, \u003ci\u003ea\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e are positive integers, \u003ci\u003ea\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e · \u003ci\u003ea\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e · … · \u003ci\u003ea\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e ≤ 512.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe input will consist of a single non-empty string \u003ci\u003eS\u003c/i\u003e with length not exceeding 10\u003csup\u003e5\u003c/sup\u003e. This string will be an outcome of calling \u003ccode\u003edeepToString\u003c/code\u003e on an array of the described type.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the number of array configurations with the given string representation modulo 10007. \r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e[[], []]\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e[[[[]]]]\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e[[[]], [[]]]\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe arrays in the third example were created by the following statements:\r\n\r\n\u003col\u003e\r\n\u003cli\u003e\r\n\u003cpre\u003e\r\nthird \u003d new Object[2][1][0];\r\n\u003c/pre\u003e\r\n\u003c/li\u003e\r\n\r\n\u003cli\u003e\r\n\u003cpre\u003e\r\nObject level1 \u003d new Object[1][0];\r\nthird \u003d new Object[] { level1, level1 };\r\n\u003c/pre\u003e\r\n\u003c/li\u003e\r\n\r\n\u003cli\u003e\r\n\u003cpre\u003e\r\nObject level2 \u003d new Object[0];\r\nthird \u003d new Object[] { new Object[] { level2 }, new Object[] { level2 } };\r\n\u003c/pre\u003e\r\n\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003c/div\u003e\u003c/div\u003e"}}]}