Alen je nedavno otkrio topforces.edu.pl, najnoviju web stranicu sa zadacima te se odmah krenuo registrirati. Napisao je svoje ime, prezime, e-mail adresu, broj telefona, kućnu adresu, poštanski broj, omiljenu pjesmu, veličinu majice te, naravno, lozinku i ponovljenu lozinku. Nakon što je kliknuo na gumb za registraciju dočekala ga je sljedeća poruka:

Lozinka se mora sastojati od točno \(N\) znamenaka te se nijedan tročlani podniz lozinke ne smije sastojati od uzastopnih znamenaka u rastućem ili padajućem poretku (npr. \(123\), \(789\), \(543\)).

Podniz nekog niza dobivamo brisanjem nekih njegovih elemenata uz očuvanje poretka neobrisanih elemenata. Primjerice, podniz \((1, 3, 5)\) dobivamo brisanjem drugog i četvrtog elementa niza \((1, 2, 3, 4, 5)\). Shodno definiciji, tročlani podnizovi \((1, 2, 9)\) i \((3, 3, 4)\) smiju se nalaziti u lozinki, dok su podnizovi \((5, 6, 7)\) i \((9, 8, 7)\) zabranjeni. Također, valjane lozinke smiju sadržavati vodeće nule.

Alen nije mogao samo tako odlučiti koju će lozinku odabrati pa je napisao program koji ispisuje ukupan broj valjanih lozinki zajedno s \(K\)-tom lozinkom po veličini koju će, u konačnici, odabrati za svoju lozinku.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi \(N\) \((1 \leq N \leq 20)\) i \(K\) iz teksta zadatka. Broj \(K\) neće biti veći od ukupnog broja valjanih lozinki.

Izlazni podaci

U prvi redak ispiši ukupan broj lozinki, a u drugi redak ispiši Alenovu lozinku.

Bodovanje

U test podacima ukupno vrijednima \(13\) bodova vrijedi \(N \leq 2\).

U test podacima ukupno vrijednima \(57\) bodova vrijedi \(N \leq 7\).

U test podacima ukupno vrijednima \(69\) bodova vrijedi \(N \leq 9\).

Rješenja koja na nekom test podatku ispisuju točan broj lozinki, a pogrešnu Alenovu lozinku ili ispisuju točnu Alenovu lozinku, a pogrešan broj lozinki, osvojit će pola bodova predviđenih za taj test podatak.

Primjeri test podataka

Ulaz

1 7

Izlaz

10
6

Ulaz

2 1

Izlaz

100
00

Ulaz

3 980

Izlaz

984
995