Qüllə#5735
Alan bina kərpiclərindən qüllələr qurmağı sevir. Onun qüllələri kvadrat əsaslı çoxlu kuboidlərdən ibarətdir. Bütün kuboidlərin hündürlüyü h = 1 eynidir. Alan ardıcıl kuboidləri bir-birinin üstünə qoyur:
Şəkil 1: Alan a_2 = 2 təyin edəndə üç kərpicdən ibarət qüllə.
Son zamanlarda riyaziyyat dərsində Alan həcmi anlayışını öyrəndi. İndi o, qülləsinin həcmini hesablamaq istəyir. Kuboidlərin əsaslarının uzunluqları (yuxarıdan aşağıya) Alan tərəfindən aşağıdakı şəkildə qurulur:
Birinci kvadratın uzunluğu a_1 birdir.
Sonra, Alan ikinci kvadratın uzunluğunu a_2 təyin edir.
Sonra, Alan uzunluğu a_n (n > 2) 2a_2a_{n-1} - a_{n-2} ilə hesablayır. Niyə belə bir formul seçdiyini soruşmayın; sadəcə deyək ki, o, həqiqətən qəribə bir gəncdir.
Məsələn, Alan a_2 = 2 təyin edərsə, onda a_3 = 8 - a_1 = 7; bax Şəkil 1. Alan a_2 = 1 təyin edərsə, onda a_n = 1 bütün n N üçün doğrudur; bax Şəkil 2.
İndi Alan N ardıcıl bina kərpiclərindən ibarət qüllənin həcmini hesablaya biləcəyini düşünür. Alana kömək edin və bu həcmi hesablayan proqram yazın. Çünki bu çox böyük ola bilər, cavabı verilmiş təbii ədəd m modulunda hesablamaq kifayətdir.
Giriş bir neçə test halını ehtiva edir. Birinci sətir test halların sayını göstərən t (t ≤ 10^5) ədədini ehtiva edir. Sonra t test halları gəlir. Onların hər biri ayrı sətirdə üç tam ədəd a_2, N, m (1 ≤ a_2, m ≤ 10^9, 2 ≤ N ≤ 10^9) ilə ayrılmış şəkildə verilir, burada a_2 ikinci kvadratın uzunluğunu addım 2-də təyin edir, N isə Alan tərəfindən qurulmuş kərpiclərin sayını göstərir.
Hər bir test halı üçün (a_2, N, m) Alan tərəfindən addımlar (1-3) üzrə qurulmuş N ardıcıl kərpicdən ibarət qüllənin həcmini hesablayın və onun m modulunda qalanını çıxarın.
Şəkil 2: Alan a_2 = 1 təyin edəndə dörd kərpicdən ibarət qüllə.
Nümunə 1