Counting Eulerian Tours in a Room-Key System

You are given n rooms, numbered from 1 to n. In each room, there are several distinct keys, each of which opens the door to a specific room. Initially you are in room $1$.

Whenever you enter a room, you must choose one of the keys present in that room, use it to go to its corresponding room, and then discard the key (i.e. throw it into the garbage).

Your goal is to use all keys (each exactly once) and finally return to room $1$, with the garbage containing all the keys. Two ways are considered different if and only if the order in which the keys are used is different.

Compute the number of valid sequences modulo $10^6+3$.

Explanation

Assume room i has $d_i$ keys (or say, there are $d_i$ edges going out from room i). Notice that every time you leave a room, you use exactly one key. For a valid sequence (which uses all keys and returns to room $1$), the process corresponds to an Eulerian cycle in the directed multigraph defined by the rooms and keys.

A necessary condition for an Eulerian cycle is that for every room i, the in‑degree equals the out‑degree. Furthermore, all rooms with at least one key (i.e. with nonzero degree) must be connected (when considered as an undirected graph) from room $1$.

If these conditions are met, then when in room i the keys can be used in any order. Hence, the number of valid sequences is

inputFormat

The first line contains an integer $n$ ($1\leq n \leq 10^5$), denoting the number of rooms.

Then follow $n$ lines. The i^th of these lines describes room $i$ and begins with an integer $k$ representing the number of keys in room $i$. Following $k$ integers represent the room number each key goes to.

It is guaranteed that all keys are distinct.

outputFormat

Output a single integer: the number of valid sequences modulo $10^6+3$.

sample

3
2 2 3
1 1
1 1

2