Very long integer

how to make array of size 1e9, also how to store it??

You cannot have such large arrays, you may use map instead if looking for DP solution and check initialization using count function