Kosmik gəmi

Корova Bessi yadplanetlilər tərəfindən qaçırılıb və indi yadplanetli kosmik gəmisində kilidlənib! Kosmik gəmidə n otaq var, 1-dən n-ə qədər nömrələnmiş, bəzi otaq cütlərini birləşdirən birtərəfli qapılar var (oyundakı yadplanetli texnologiyasının qəribəliyi səbəbindən, bir otaqdan olan qapı hətta özünə geri də apara bilər). Lakin heç bir iki qapı eyni başlanğıc və son otağa malik deyil. Bundan əlavə, Bessinin 1-dən k-ə qədər nömrələnmiş düymələri olan bir pultu var.

Yadplanetlilər Bessini azad edəcəklər, əgər o qəribə bir tapşırığı yerinə yetirə bilsə. Əvvəlcə onlar iki otaq s və t və iki ədəd b[s] və b[t] (1 ≤ b[s], b[t] ≤ k) seçəcəklər. Onlar Bessini s otağına buraxacaqlar və dərhal onu b[s] düyməsini basmağa məcbur edəcəklər. Sonra Bessi gəmidə naviqasiya etməyə davam edəcək, düymələri basaraq. Bessinin edə biləcəyi bir neçə qayda var:

• Hər otaqda bir düyməni basdıqdan sonra o, ya başqa (bəlkə də eyni) otağa qapıdan çıxmalı, ya da dayanmalıdır.

• Bessi bir düyməni basdıqdan sonra, həmin düyməni təkrar basa bilməz, əgər arada daha böyük nömrəli bir düyməni basmasa. Başqa sözlə, x nömrəli düyməni basmaq onu istifadəyə yararsız edəcək və x-dən kiçik nömrəli bütün düymələr sıfırlanacaq və yenidən istifadəyə yararlı olacaq.

• Əgər Bessi səhv düyməni basarsa, o avtomatik olaraq uğursuz olacaq və yadplanetlilər onu buraxmayacaq.

Bessi yalnız o halda azad ediləcək ki, o t otağında dayansın, basdığı son düymə b[t] olsun və heç bir səhv düymə basılmasın.

Bessi narahatdır ki, o tapşırığı yerinə yetirə bilməyəcək. q sorğu üçün, hər biri s, t, b[s] və b[t] dəstindən ibarət olan, Bessi azad olunmasına gətirib çıxaracaq otaq və düymə basma ardıcıllıqlarının sayını bilmək istəyir. Cavablar çox böyük ola biləcəyi üçün onları 10^9 + 7 moduluna görə çıxarın.

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 60), k (1 ≤ k ≤ 60), q (1 ≤ q ≤ 60) ədədlərini ehtiva edir. Növbəti n sətirin hər biri n bit (hər biri 0 və ya 1) ehtiva edir. i-ci sətirdəki j-ci qeyd, əgər i otağından j otağına qapı varsa 1, əks halda 0 ehtiva edir.

Daha sonra q sətir gəlir, hər biri dörd tam ədəd b[s], s, b[t], t (1 ≤ s, t ≤ n) ehtiva edir, başlanğıc düymə, başlanğıc otaq, son düymə və son otağı müvafiq olaraq göstərir.

Çıxış məlumatları

Hər bir q sorğu üçün ardıcıllıqların sayını 10^9 + 7 moduluna görə ayrı-ayrı sətirdə çıxarın.

Nümunə

Qapılar otaqları 1 → 2, 2 → 3, 3 → 4, 4 → 5 və 6 → 6 birləşdirir.

Birinci sorğu üçün Bessi ilk düyməni basdıqdan dərhal sonra dayanmalıdır.

İkinci sorğu üçün cavab sıfırdır, çünki 3 otağından 1 otağına keçmək mümkün deyil.

Üçüncü sorğu üçün Bessinin yeganə seçimi 1 otağından 2 otağına, sonra 3 otağına keçməkdir, 1, 2 və 3 düymələrini basaraq.

Dördüncü sorğu üçün Bessinin hərəkət tərzi sabitdir və onun düymə basma ardıcıllığı üçün üç mümkün variantı var:

(1,2,3,2,1)
(1,2,1,3,1)
(1,3,1,2,1)

Son sorğu üçün Bessinin beş mümkün düymə basma ardıcıllığı var:

(2)
(2,3,2)
(2,3,1,2)
(2,1,3,2)
(2,1,3,1,2)