Програмчлалын багш Дмитрий Олегович дараах бодлогоор оюутнуудаас шалгалт авахаар болов.

Танд $a[1... n, 1... n]$ матрицаар оройнуудын холбоог илэрхийлсэн $n$ оройтой $T$ мод өгөгдөнө. Дараах псевдо кодын үр дүнд үүсэх гаралт нь юу байх вэ?

used[1 ... n] = {0, ..., 0};  

procedure dfs(v):  
    print v;  
    used[v] = 1;  
    for i = 1, 2, ..., n:  
        if (a[v][i] == 1 and used[i] == 0):  
            dfs(i);  

dfs(1);

Дмитрий Олегович шалгалтын хариуг хялбархан шалгах зорилгоор үр дүн нь түүний дуртай $b$ дараалал байх $T$ модыг үүсгэхээр шийджээ. Нөгөө талаас Дмитрий Олегович оролтонд адилхан мод оюутнуудад өгөхийг хүсэхгүй байгаа, учир нь тэд нэг нэгнээсээ хуулж магадгүй юм. Тиймээс Дмитрий дээрх псевдо кодны оролт нь $T$ мод, гаралт нь $b$ дараалал байх ялгаатай $T$ моднуудын тоог олохыг хичээж байна. Та түүнд тусалж чадах уу?

Хэрэв оройнуудын холбоог илэрхийлсэн $a_{1}$ ба $a_{2}$ матрицууд ялгаатай бол $n$ оройтой хоёр модыг ялгаатай гэнэ. Өөрөөр хэлбэл $1 ≤ i, j ≤ n$ ба $a_{1}[i][j] ≠ a_{2}[i][j]$ байх $(i, j)$ хос байна.

Оролт

Эхний мөр нь $b$ дарааллын урт болох эерэг бүхэл $n$ ($1 ≤ n ≤ 500$) тоог агуулна.

Хоёр дахь мөр нь $n$ ширхэг $b_{1}, b_{2}, ..., b_{n}$ ($1 ≤ b_{i} ≤ n$) эерэг бүхэл тоонуудыг агуулна. $b$ нь $n$ хүртэлх тооны сэлгэмэл байна. Өөрөөр хэлбэл $b$ дараалалд $1, 2, ..., n$ тоонууд яг нэг удаа л тохиолдоно. Мөн $b_{1} = 1$ байна.

Гаралт

Дээрх нөхцлийг хангасан моднуудын тоог $10^{9} + 7$-д хуваагаад үлдэгдлийг хэвлэнэ үү.