You are a fan of “Internet of Things”(IoT), so you build a nice Internet of Lights and Switches in your huge mansion. Formally, there are n lights and m switches, each switch controls one or more lights, i.e. pressing that switch flips the status of those lights (on → off, off → on). Initially, all the lights are on. Your task is to count the number of ways to turn off all the lights by pressing some consecutive switches. There is only one restriction: the number of switches you pressed should be between a and b (inclusive). Input There will be at most 20 test cases. Each test case begins with a line containing four integers n, m, a, b(2≤n≤50,1≤a≤b≤m≤300000). Eachofthefollowingmlinescontainsa01stringoflength n. The i-th character is ‘1’ if and only if that switch controls the i-th light. The size of the whole input file does not exceed 8MB. Output For each test case, print the case number, and the number of ways to turn off all the lights. Sample Input 2414 01 10 11 00 2433 01 10 11 00 6313 101001 010110 101001
2/2 Sample Output Case 1: 3 Case 2: 0 Case 3: 2