Аль-Фараби тақтаға өз ұнататын \(n\) бүтін саннан тұратын тізбегін жазды: \(a_1, a_2, \dots, a_n\). Біршама уақыттан кейін Мақан келіп, тақта лас деп ойлап, бәрін өшіріп тастады. Кейін ол Аль-Фарабидің тізбегін өшіріп алғанын түсінді.

Енді Мақанға барлық сандарды еске түсіру өте қиын — олар өте көп болған. Сол үшін ол кем дегенде қанша әртүрлі тізбек тақтада жазылуы мүмкін екенін есептеп, Аль-Фарабиге қуаныш сыйлағысы келеді.

Мақан тізбекке қатысты екі қасиетті еске сақтаған:

1. Әрбір сан теріс емес және \(2^b\)-нен кем. Яғни, әрбір \(1\le i\le n\) үшін \[0 \le a_i < 2^b.\]

2. Тізбектегі барлық ұзындығы \(b\) болатын ішкі тізбектер «жақсы» деп табылады. Ұзындығы \(b\) болатын ішкі тізбек \(a_l, a_{l+1}, \dots, a_{l+b-1}\) "жақсы" деп аталады, егер \[a_l\;|\;a_{l+1}\;|\;\dots\;|\;a_{l+b-1} = 2^b - 1,\] мұнда \(|\) — биттік "НЕМЕСЕ" (битwise OR) операциясын білдіреді¹.

Осы шарттарды қанағаттандыратын ұзындығы \(n\) болатын тізбектердің саны қанша екенін Мақанға анықтауға көмектесіңіз. Жауап өте үлкен болуы мүмкін болғандықтан, оны \(10^9+7\) модулі бойынша шығарыңыз.

Енгізу

Бірінші және жалғыз жолда екі бүтін сан бар: \(n\) және \(b\) (\(1 \le b \le 30,\; b \le n \le 10^{12}\)) — тізбектің ұзындығы және "жақсы" ішкі тізбекті анықтайтын \(b\) саны.

Шығару

Шығырыңыз — бір бүтін сан: Аль-Фараби тақтаға жазған болуы мүмкін тізбектер санының \(10^9+7\) модулі.

Бағалау жүйесі

Бұл тапсырмада \(6\) қосалқы тапсырма бар.

Мысалдар

Енгізу 1

3 2

Жауап 1

25

Енгізу 2

13 9

Жауап 2

490181292

Ескертпелер

Бірінші мысалда әр ұзындығы \(2\) болатын подотрезк (яғни, әрбір көршілес жұп) биттік ИЛИ арқылы \(2^b-1 = 3\) мәнін беруі тиіс. Қорыта келгенде, осындай тізбектердің жалпы саны \(25\). Мысалы, Аль-Фарабиның ұнатқан тізбегінің біреуі болуы мүмкін: \([3,1,3]\) немесе \([2,3,0]\).