Coffee Brand Switching

A market researcher tracks which coffee brand shoppers buy each month. From loyalty-card data she has a switching table P: P[a][b] is the probability that a shopper who bought brand a this month buys brand b next month. Each row adds up to 1, and a missing entry means probability 0. What a shopper buys next month depends only on what they bought this month.

Write shares_after(P, shares, months) that returns the market shares months months from now, as a dict with one entry for every brand in P. shares gives this month's share of shoppers buying each brand (a missing brand has share 0).

Examples

Input:  P = {"Arabica": {"Arabica": 0.8, "Bold": 0.15, "Crema": 0.05},
             "Bold":    {"Arabica": 0.1, "Bold": 0.7,  "Crema": 0.2},
             "Crema":   {"Arabica": 0.3, "Bold": 0.1,  "Crema": 0.6}}
        shares = {"Arabica": 0.5, "Bold": 0.3, "Crema": 0.2}, months = 1
Output: {"Arabica": 0.49, "Bold": 0.305, "Crema": 0.205}
Explanation: next month's Arabica share is 0.5 * 0.8 + 0.3 * 0.1 + 0.2 * 0.3 = 0.49.

Input:  the same P and shares, months = 2
Output: {"Arabica": 0.484, "Bold": 0.3075, "Crema": 0.2085}

Constraints

• 1 <= len(P) <= 30; every brand that appears in a row or in shares is a key of P
• 0 <= months <= 1000
• floats are compared with a tolerance of 1e-6

Goals

• Read a transition table as the probabilities of the next state given the current one
• Push a probability distribution through the table one step at a time
• Handle missing entries (probability 0) and zero steps