Valid Passwords

Problem Overview

• Count distinct passwords of length n using lowercase letters that avoid k consecutive identical characters.
• Input: integers n and k; Output: number of valid passwords modulo 1,000,000,007; Constraints: 2 ≤ n ≤ 1e5, 2 ≤ k ≤ n.
• Banking security context (Hackerbank in Hackerland) modeling password policy.
• From Mathworks interviews; a coding interview problem and common interview question on counting valid strings.