Masala #0944
Qism to`plam yig`indisi #2
Bu masalaning oson va qiyin versiyalarining yagona farqi n dagi chegarasidadir.
1 dan \(n\) gacha barcha natural sonlardan tashkil topgan to`plam mavjud. Sizning vazifangiz shu to`plamdagi sonlari yig`indisi \(m\) ga karrali barcha qism to`plamlar sonini topishdan iboratdir. Natija juda katta son bo`lishi mumkinligi sababli uni \(10^9+7\) ga bo`lgandagi qoldig‘ini chiqaring.
Yagona qatorda ikkita butun son - \(n(1 \leq n \leq 10^{18})\) va \(m(1 \leq m \leq 30)\) beriladi.
Bitta butun son — natijaning \(10^9+7\) ga bo‘lgandagi qoldig‘ini chiqaring.
# | input.txt | output.txt |
---|---|---|
1 |
5 5 |
8 |
2 |
17 19 |
6899 |
1-testda shartni qanoatlantiradigan qism to‘plamlar quyidagilardir: {}, {5}, {1,4}, {2,3}, {1,4,5}, {2,3,5}, {1,2,3,4}, {1,2,3,4,5}.