Project: Valid Code-Set Counter for Binary Transforms

A tiny Python program that reads a binary string and computes:

1. How many valid code sets X (made of codes from {0,1} with length ≤ 3, no prefixes) can greedily transform the string (left-to-right) into a sequence of codes; and
2. The total number of alphabetic labelings for those valid sets (assuming each code maps to a distinct English letter), reported mod 1,000,000,007.

This matches the assignment spec (Discrete Math final project): input is a binary string of length ≤ 100; output is the count of valid sets and the sum of labelings, both as integers.

---

Contents

• main.py — the whole solution (rename your script to this if needed)

---

How it works (quick)

• check_valid_set(x): validates a set X
  • non-empty, codes only 0/1, each length ≤ 3, no code is a prefix of another.
• transform_condition(x, string): greedy left-to-right parsing; succeeds iff the string can be consumed entirely using codes from X, and each code appears at least once.
• comb(x, n): builds all size-n combinations (lexicographic, no repeats).
• process_subsets(binary_string): enumerates all candidate X ⊆ {'0','1','00','01','10','11','000','001','010','011','100','101','110','111'}, filters by the two checks above.
• Final tally:
  • Prints |{ valid X }|.
  • Then computes, for each set of size k, the number of labelings 26·25·…·(26−k+1) and sums them mod 1e9+7.

Note: The parsing is greedy (startswith + break). That matches the stated transform rule in the brief.

---

Requirements

• Python ≥ 3.8
• No third-party libraries

---

Usage

python main.py
# then paste a binary string and press Enter

Or with a file:

python main.py < input.txt

Input: a single line binary string (length ≤ 100). Output: two lines:

1. number of valid sets X
2. sum of labelings modulo 1,000,000,007

---

Examples

Input
001

Output
3
1326

Input
0101010

Output
4
2600

Input
01110

Output
5
18200

---

Performance notes

• The search space is all subsets of up to 14 candidate codes (length ≤ 3), filtered by validity; the brute-force combination generation is exponential in the worst case. This is OK for short inputs (≤100 bits), but:
  • You can prune further by rejecting any set that has a prefix conflict earlier (already done), or by prechecking coverage (e.g., if a set contains no code starting with the input’s first bit, skip).
  • Memoizing transform_condition by (tuple(X), start_index) would avoid repeated scans.

---

File structure

.
└── main.py

Rename your provided script to main.py (or adjust commands accordingly).

---

Testing quickly

Create input.txt:

001

Run:

python main.py < input.txt

Expected:

3
1326