1. Числа−2
(за матеріалами ІІІ (міського) етапу 2012 року)

Максимальна оцінка: 100 балів
Обмеження на час: 1,5 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: numbers.in
Вихідний файл: numbers.out
Програма: numbers.*

      Завдання
      Дано три цілих числа N, a і b. Потрібно знайти залишок від ділення на число 1 000 000 007 (10⁹ + 7) кількості натуральних чисел X, для яких одночасно справджуються такі три умови:
1) X ≤ N;
2) X кратне 2^a;
3) сума цифр числа X кратна 2^b.

      Вхідні дані
      Перший рядок вхідного файлу містить 2 цілих числа: a та b (0 ≤ a ≤ 9, 0 ≤ b ≤ 9).
      Другий рядок містить число N (1 ≤ N ≤ 10⁵⁰⁰⁰).

      Вихідні дані
      Вихідний файл має містити одне число — залишок від ділення на число 1 000 000 007 (10⁹ + 7) кількості натуральних чисел X, для яких справджуються усі умови 1–3, подані вище.

      Приклади

      Пояснення
      Лише числа 4, 8 і 20 задовольняють умову другого прикладу.

      Зауваження щодо оцінювання

1. У 15% тестів 1 ≤ N ≤ 1 000 000.
2. Ще у 15% тестів b = 0.
3. Ще у 15% тестів a = 0.
4. Ще у 20% тестів N ≤ 10⁵⁰⁰, a ≤ 4, b ≤ 4.
5. У решті 35% тестів жодних обмежень на змінні, крім описаних у секції «Вхідні дані», не накладено.

2. Розклад уроків
(за матеріалами ІІІ (міського) етапу 2011 року)

Максимальна оцінка: 100 балів
Обмеження на час: 0,3 сек.
Обмеження на пам’ять: 32 Mб
Вхідний файл: schedule.in
Вихідний файл: schedule.out
Програма: schedule.*

Уявіть, що Вам потрібно скласти розклад уроків на тиждень. Для кожного класу відомо, які предмети мають викладати у цьому класі та скільки уроків припадає на кожен предмет. Кожний предмет викладає лише один учитель, тому уроки з одного предмета не можуть бути у двох класах одночасно. Уроки мають суцільну нумерацію: наприклад, якщо у школі щодня буває не більше за 7 уроків, то перший урок вівторка має номер 8, другий урок вівторка — номер 9 і т. д. Уроки з одним і тим самим номером проходять для всіх класів у один і той самий час. У розкладі допускають «вікна» — випадки, коли один або декілька уроків пропускають, а перед цим і після цього уроки проводять.

Завдання
Подайте приклад потрібного розкладу або вкажіть, що розв’язку немає.

Вхідні дані
Перший рядок вхідного файлу містить у вказаному порядку цілі числа N (1 ≤ N ≤ 50) та T (1 ≤ T ≤ 50), де N — кількість класів, а T — максимально можлива кількість уроків протягом тижня. Кожний з наступних N рядків задає перелік предметів, уроки з яких потрібно проводити у відповідному класі (по рядку на клас). У кожному такому рядку записано T невід’ємних цілих чисел:

• кожен предмет позначено деяким натуральним числом від 1 до 50 (ця нумерація спільна для всіх рядків);

• номер кожного предмета зустрічається у рядку стільки разів, скільки уроків протягом тижня припадає на цей предмет у відповідному класі;

• якщо рядок містить менше ніж T натуральних чисел, він доповнений такою кількістю нулів, щоб загальна кількість чисел у ньому дорівнювала T. Інакше кажучи, кількість нулів — це кількість уроків, які клас пропускає.

Позначимо через Q(i, j) кількість чисел, які дорівнюють j й розташовані у рядку, що задає перелік предметів для i-го класу (1 ≤ i ≤ N). При 1 ≤ j ≤ 50 справджується така нерівність:

Інакше кажучи, розклад потрібно скласти за умови, що кожному вчителю призначено провести протягом тижня не більше ніж T уроків.

Вихідні дані
Вихідний файл має містити N рядків по Т чисел. Для k = 1, 2, …, N у k-му рядку вихідного файлу має бути заданий розклад для класу, описаного (k + 1)-м рядком вхідного файлу. Кожне число у k-му рядку вихідного файлу має траплятися стільки разів, скільки воно трапилося у (k + 1)-му рядку вхідного файлу. При кожному j (1 ≤ j ≤ T) на j-х місцях різних рядків не може бути однакових додатних чисел — нулів це не стосується. Якщо шуканих розкладів багато, подайте будь-який з них. Якщо потрібного розкладу немає, виведіть число –1.

Приклади