Cyclic Cafeteria Menu Planner

TimeTraveller is a devoted foodie who, instead of registering for classes on his first day of school, decided to investigate the cafeteria dishes. Unfortunately, for various reasons the cafeteria offers only a few dishes each semester. In fact, the cafeteria has fixed menus for a few days and then cycles through these menus repeatedly throughout the semester.

TimeTraveller finds this repetitive menu cycle quite demoralizing, but he has one consolation: he only cares that the dishes he eats on consecutive days are not the same. In other words, he is fine with eating the same dish if there is a break of at least one day. However, being a true foodie, he insists on eating at least one dish every day.

More formally, you are given a cycle of k menus. The semester lasts for n days. For the i-th menu (1 ≤ i ≤ k), a list of available dishes is provided (each dish is identified by an integer). The daily menu on day i of the semester is the menu number ((i-1 mod k) + 1). On each day, TimeTraveller must choose a nonempty subset of the dishes available on that day. However, his planning must satisfy the condition that the set of dishes chosen on day i and the set chosen on day i+1 have no dish in common (for every 1 ≤ i < n).

Your task is to compute the total number of valid meal planning methods over the semester. As the answer might be very large, output it modulo \(10^9+7\).

Note on subsets: For a menu with \(r\) dishes, there are \(2^r - 1\) nonempty subsets to choose from.

Input Format:

• The first line contains two integers \(n\) and \(k\): the number of days in the semester and the length of the menu cycle.
• The following \(k\) lines each describe a menu. Each of these lines starts with an integer \(r\) (the number of dishes available that day), followed by \(r\) space‐separated integers denoting the dish IDs.

Output Format:

• Output a single integer: the number of valid planning methods modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(k\) (1 ≤ n, k ≤ 10⁵ in typical constraints, though for this problem the menus are small).

Each of the next \(k\) lines contains an integer \(r\) followed by \(r\) integers, representing the dish IDs available on that menu day. The menus are 1-indexed and the day i in the semester uses the menu at index \(((i-1) mod k) + 1\).

outputFormat

Output one integer: the number of valid meal planning ways modulo \(10^9+7\).

sample

1 2
2 1 2
2 2 3

3