Inspired by the recent 3Blue1Brown video
Consider, for some positive integer \$n\$, the set \$\{1, 2, ..., n\}\$ and its subsets. For example, for \$n = 3\$, we have
$$\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$$
If we take the sum of these subsets, we can then ask ourselves the following question:
Of the sums of the subsets of \$\{1, 2, ..., n\}\$, how many are divisible by some given integer \$k\$?
Again, using \$n = 3\$ as an example, we have our subset sums as
$$0, 1, 2, 3, 3, 4, 5, 6$$
For \$k = 2\$, there are \$4\$ subsets whose sum is divisible by \$k\$: \$\emptyset, \{2\}, \{1,3\}\$ and \$\{1,2,3\}\$.
Given two positive integers \$n \$ and \$k\$, with \$2 \le k \le n\$, output the number of subsets of \$\{1, 2, 3, ..., n-1, n\}\$ such that their sum is divisible by \$k\$.
You may take input and give output in any reasonable manner and format. This is code-golf, so the shortest code in bytes wins.
Test cases
n k out
3 2 4
5 5 8
13 8 1024
2 2 2
7 7 20
14 4 4096
15 10 3280
9 5 104
7 2 64
11 4 512
15 3 10944
16 7 9364
13 5 1640
11 6 344
12 10 410
9 9 60
And, a couple of larger ones, taken from the approach in the 3Blue1Brown video:
200, 5 -> 321387608851798055108392418468232520504440598757438176362496
2000, 5 -> 22962613905485090484656664023553639680446354041773904009552854736515325227847406277133189726330125398368919292779749255468942379217261106628518627123333063707825997829062456000137755829648008974285785398012697248956323092729277672789463405208093270794180999311632479761788925921124662329907232844394066536268833781796891701120475896961582811780186955300085800543341325166104401626447256258352253576663441319799079283625404355971680808431970636650308177886780418384110991556717934409897816293912852988275811422719154702569434391547265221166310540389294622648560061463880851178273858239474974548427800576