Shafi is partitioning an intercepted continuous stream of cryptographic data, represented as a string S of N digits, into valid contiguous blocks.

To prove the integrity of the data stream without revealing its exact contents, she implements a strict protocol. A partition of the string is considered valid if and only if it satisfies all of the following conditions:

Threshold Rule Every block's numerical value (when read as a base-10 integer) must be less than or equal to K. Leading Zero Rule A block cannot contain any leading zeros, unless the block consists of exactly the single digit "0". XOR-Length Cipher The bitwise XOR of all the individual digits inside a block must be exactly equal to the length of that block. Anti-Frequency Protocol No two adjacent blocks in the partition can have the same length.

Given the string of digits S and the threshold number K (provided as a string since it can be very large), determine the total number of valid partitions of S.

Since the answer can be very large, output it modulo 10^9 + 7.

Input Format The first line contains a single integer N, the length of the intercepted data stream. The second line contains the string S, consisting of N digits (0-9). The third line contains the string K, consisting of up to 10^5 digits (0-9) with no leading zeros. Output Format

Output a single integer: the total number of valid partitions modulo 10^9 + 7.

Sample 1 Input 3 113 1000 Output 2 Explanation (partially visible in the image)

For S = "113":

The valid blocks satisfy:

Threshold Rule (≤ 1000) Leading Zero Rule XOR-Length Rule Adjacent blocks cannot have the same length

There are 2 valid partitions.