Gegeven een getal \(n\) en een verzameling \(M=\{d_1,\dots ,d_k\}\) van kleinere positieve getallen. Het doel is om te bepalen op hoeveel manieren je \(n\) als som van getallen uit \(M\) kan voorstellen — waarbij elk getal natuurlijk meerdere keren mag voorkomen.

Implementeer een \(O(n)\) tijdsbegrensd algoritme voor dit probleem.

Je kan deze oefening op twee manieren interpreteren:

• verschillende volgordes tellen als verschillende manieren — dus \(5=1+1+2+1\) verschilt van \(5= 2+1+1+1\)
• de volgorde is niet belangrijk — manieren om \(n\) als som van getallen uit \(M\) te schrijven tellen alleen als verschillend als de getallen \(d_1,\dots ,d_k\) niet even vaak voorkomen, dus \(5=1+1+2+1\) verschilt niet van \(5=2+1+1+1\), maar wel van \(5=2+2+1\).

Volg hier de tweede manier, waar de volgorde niet belangrijk is.

Implementeer hiervoor de interface Som¹ in een klasse genaamd SomDynamisch. Geef het antwoord modulo \(1000000009\) om overflow te voorkomen.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen.