标签: 原根

「2017 四川省赛」2017 Revenge

Bobo has n integers a1,a2,,ana_1, a_2, \dots, a_n
He would like to choose some of the integers and calculate their product (the product of the empty set is defined as 1).

Bobo would like to know the number of products whose remainder divided by 2017 is r. As the exact number is too large, he only asks for the number modulo 2.