Lozinka

시간 제한1초메모리 제한1024 MB

요약

길이 N인 숫자열 가운데 3개를 골라 만든 부분수열이 연속한 세 숫자의 오름차순이나 내림차순이 되지 않는 것의 개수를 세고, K번째로 작은 수열을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

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.

입력

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

출력

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

예제3

예제 1
입력
```
1 7
```
예상 출력
```
10
6
```
예제 2
입력
```
2 1
```
예상 출력
```
100
00
```
예제 3
입력
```
3 980
```
예상 출력
```
984
995
```