| Fişierul intrare/ieşire: | num.in, num.out | Sursă | RMI 2021 |
| Autor | Alexandru Petrescu | Adăugată de |  Popovici Robert •PopoviciRobert |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Num
Marcel s-a apucat recent de un nou hobby:~crearea grădinilor zen. Şi-a dezvoltat rapid propriul stil, care foloseşte 2N pietre drept decoraţiuni de grădină. Jumătate de pietre sunt verzi (sunt acoperite cu muşchi) şi sunt numerotate unic de la 1 la N, în timp ce cealaltă jumătate sunt gri (nu creşte muşchi pe ele) şi sunt de asemenea numerotate unic de la 1 la N. În vederea creării unei grădini, Marcel va lua pietrele şi le va plasa într-o anumită ordine în linie dreaptă, asigurându-se că distanţa dintre oricare două pietre consecutive este exact 1 inch.
Când vine vorba de a judeca aspectul estetic al unei grădini, toate grădinile sunt considerate frumoase. Cu toate acestea, există o superstiţie pe care Marcel o are despre grădinile sale:~dacă distanţa dintre două pietre care au acelaşi număr scrie pe ele este egală cu un multiplu de M inchi, atunci grădina este considerată M- ghinionistă, aducând mare ghinion şi abătând erori Code::Blocks asupra celui care a creat grădina respectivă. Marcel nu va crea niciodată o astfel de grădină. În mod normal, restul grădinilor sunt considerate M- norocoase.
Ca parte din aventura lui de a dobândi înţelepciune, Marcel a decis să creeze toate grădinile M- norocoase posibile. În orice caz, fiind de asemenea şi un individ precaut şi organizat, Marcel şi-ar dori să afle câte grădini M- norocoase conţinând 2N pietre există înainte să plece în misiunea lui. Două grădini A şi B sunt considerate diferite dacă există un număr întreg i, 1 ≤ i ≤ 2N, astfel încât:
- culoarea celei de-a i-a pietre din grădina A este diferită de culoarea celei de-a i-a pietre din grădina B, sau
- numărul scris pe a i-a piatră din grădina A este diferit de numărul scris pe a i-a piatră din grădina B.
Date de intrare
Fişierul de intrare num.in conţine două numere întregi N şi M, cu seminficaţia că Marcel va crea grădini cu 2N pietre care sunt M-*norocoase*.
Date de ieşire
În fişierul de ieşire num.out se află o singură linie, afişaţi numărul de grădini M-norocoase care conţin 2N pietre, modulo 109+7.
Restricţii
- 1 ≤ M ≤ N ≤ 2.000
Punctare
Punctajele fiecărui subtask sunt puţin diferite faţă de cele din concursul oficial.
- Subtask 1 de 9 puncte: N ≤ 5
- Subtask 2 de 12 puncte: N ≤ 100
- Subtask 3 de 13 puncte: N ≤ 300
- Subtask 4 de 18 puncte: N ≤ 900
- Subtask 5 de 48 de puncte: fără alte restricţii
Exemplu
| num.in | num.out |
|---|---|
| 100 23 | 171243255 |
| 1 1 | 0 |
Explicaţie
În al doilea exemplu, pot fi create două grădini. Cu toate acestea, nicio grădină nu este 1-norocoasă, întrucât pentru ambele grădini distanţa dintre pietrele numerotate cu 1 este 1 inch, care este un multiplu de M = 1 inchi.
