Shavkat juda tejamkor va hamisha o’qishga avtobusda qatnaydi.  Avtobusga minishdan yana bir maqsadi unga bilet olgan vaqtda uning baxtli bilet ekanligini tekshirib ko’rish. Bu uning sevimli mashg’uloti. Urganch shahrida avtobus bileti 2n xonali son bo’lib(nol bilan boshlanishi mumkin), agar uning dastlabki n ta xonasi raqamlari yig’indisi oxirgi n ta xonasi raqamlari yig’indisiga teng bo’lsa va juft o’rindagilar yig’indisi toq o’rindagilar yig’indisiga teng bo’lsa bu baxtli bilet deb aytiladi. Bu qanchalik foydali ekanligini bilish uchun endi u 2n xonali sonlar ichida jami nechta baxtli bilet borligini hisoblab topmoqchi. Bu ish juda qiyin bo’lganli uchun unga bu ishda yordam bering.

Kiruvchi ma’lumotlar: Yagona satrda n(1 ≤ n ≤ 500) butun son.

Chiquvchi ma’lumotlar: Yagona satrda baxtli biletlar sonini chiqaring. Javob yetarilcha kata bo’lishi mumkin shuning uchun javobni 10⁹ + 7 ga bo’lgandagi qoldiqni chiqaring.