It's Foo's birthday and a geek as Poo is, he has gifted her a binary tree with every node having 0 or 1. They were having fun with a big cake and candle lit setup when Foo got a call against one of her applications to one of the tech giants. Now she needs to prepare for her interview and Poo takes it on himself to prepare her for the interview.
To start the preparations, Poo asks Foo a problem on the binary tree he just gifted her. Since Foo is not in a mood to spoil the night, she asks for your help. Poo has asked her to extract the inorder traversal of the tree and keep a copy of it on the table.
Now Poo is going to pick up a node and give it to Foo. Foo has to traverse that subtree and form an array. After this extraction let us say M is the size of the new string and N is the size of the string we got from the inorder traversal of the whole tree. Foo has to now extract every substring of size M from the previous string and calculate the number of set bits in exclusive-xor of the two binary strings and sum those all up and get a number X. For generation of the new string, Foo can use any traversal (preorder(NLR), postorder(LRN) or inorder(LNR)) but Poo wants her to maximize the value of X by her choice.
Please help he determining the highest possible value of X.
See sample example for more explanation.

Input :

• First line of input contains the binary tree in the form of a string, in which for each char at ith position, it's left child will be at (2*i + 1) and right child will be at (2*i + 2) position (0 based indexing).
• Second line of input contains the Node index, the subtree of which, Foo have to consider.

Output :

• Output the maximum value Foo can achieve mod 1000000007.

Constraints :

• 1 ≤ N ≤ 2*10^5, where N is the number of nodes in the binary tree.
• Every node will have value 0 or 1.