「想要我的財寶嗎？想要的話可以全部給你。」
「去找吧！我把所有的財寶都放在那裡了。」
衝著這句話，珣老大即將率領船員們到各個島嶼探險，尋找傳說中的寶藏。
海上有太多島嶼了，珣老大必須擬定計畫，來最佳化他們的尋寶路徑，但優化路徑的難題交給珣老大就行了，身為船員的我們，無聊來算一下所有可能路徑的總和數吧！
海上總共有 n 個島嶼，有些島嶼們彼此距離太遠，不適合直航。且因為洋流以及天候的關係，即使甲島嶼能直航乙島嶼，乙島嶼也不一定適合直航回甲島嶼。
除此之外，不排除重複多次抵達同個島嶼的狀況。因為有些船員比較粗心，不太可能每次都能將自己負責的部分完整搜刮完畢，而珣老大是個細心的人，若發現有遺漏之處，會要求他們回去重新搜索一次。
關於路徑總數的算法以及定義，詳見範例說明。
第一行為一個正整數 n ，表示海上總共有 n 個島嶼，島嶼的編號為 1~n。
接下來 n 行，會照著島嶼編號順序來輸入各個島嶼的航行資訊。每行會先出現一個不超過n的整數 $m_k$，代表編號為 k 的島嶼在總共可以直接航行至$m_k$ 個島嶼，在 $m_k$ 後會有 $m_k$ 個數字，代表該島嶼可以直航的島嶼編號。
再接下來會有兩個正整數 q,t，表示總共有 q 筆詢問，且珣老大想要在海上航行 t 次。
最後會有 q 行，每行會有兩個正整數 a,b ，表示詢問若以編號為 a 的島嶼為起點，經過 t 次航行後，有幾種路徑會使終點為 b。
若在同一行有多個數字，皆會以空白隔開。
請輸出 q 行，每一行輸出該筆詢問的答案除以 1000000007 的餘數。
1 1 1 1 3 1 1
1
3 1 2 3 1 2 3 2 1 2 2 3 1 1 3 2
2 4
以下為兩個範例的說明，請務必參考。
範例1說明
島上只有1個島嶼，且可以從1號島嶼直航回1號島嶼。
故航行3次後，從1號島嶼至1號島嶼的路徑數只有一種：
1： 1 -> 1 -> 1 -> 1。
範例2說明
島上有3個島嶼，1號島嶼可以直航至2號島嶼，2號島嶼可以直航至1,2,3號島嶼，3號島嶼可以直航至1,2號島嶼。總共有2筆詢問，且2筆詢問都是考慮航行3次的狀況。
從1號島嶼至1號島嶼，航行3次的路徑數有2種：
1： 1 -> 2 -> 2 -> 1。
2： 1 -> 2 -> 3 -> 1。
從3號島嶼至2號島嶼，航行3次的路徑數有4種：
1： 3 -> 1 -> 2 -> 2。
2： 3 -> 2 -> 1 -> 2。
3： 3 -> 2 -> 2 -> 2。
4： 3 -> 2 -> 3 -> 2。
測資限制
1.1 ≤ n ≤ 130
2.1 ≤ t ≤ 1000
3.1 ≤ q ≤ 20000
評分說明
本題共有三組子任務，每一組有多筆測試資料，條件如下所示：
1 .n ≤ 6 , t ≤ 8 , q ≤ 5。(40%)
2 .n ≤ 60 , t ≤ 30。(30%)
3.無額外限制。(30%)
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||