Zero Knowledge Proof Partition - ICPC Algoqueen 2026

Problem Preview

"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."