SP339 SEQ - Recursive Sequence

Sequence _(a $ _{i} $ )_ of natural numbers is defined as follows: _a $ _{i} $ = b $ _{i} $_ (for _i k_) where _b $ _{j} $_ and _c $ _{j} $_ are given natural numbers for _1

On the first row there is the number _C_ of test cases (equal to about 1000). Each test contains four lines: _k_ - number of elements of _(c)_ and _(b)_ (_1

Exactly _C_ lines, one for each test case: _a $ _{n} $_ modulo _10 $ ^{9} $_